Title

On Global Domination Critical Graphs

Keywords

Changing and unchanging; Domination; Global domination

Abstract

A dominating set of a graph G = (V, E) is a subset S ⊆ V such that every vertex not in S is adjacent to at least one vertex of S. The domination number of G is the cardinality of a smallest dominating set. The global domination number, γg (G), is the cardinality of a smallest set S that is simultaneously a dominating set of both G and its complement over(G, -). Graphs for which γg (G - e) > γg (G) for all edges e ∈ E are characterized, as are graphs for which γg (G - e) < γg (G) for all edges e ∈ E whenever over(G, -) is disconnected. Progress is reported in the latter case when over(G, -) is connected.

Publication Date

10-6-2009

Publication Title

Discrete Mathematics

Volume

309

Issue

19

Number of Pages

5894-5897

Document Type

Article

Personal Identifier

scopus

DOI Link

https://doi.org/10.1016/j.disc.2008.06.005

Socpus ID

70349121778 (Scopus)

Source API URL

https://api.elsevier.com/content/abstract/scopus_id/70349121778

This document is currently not available here.

Share

COinS