Domination critical graphs with respect to relative complements

Teresa W. Haynes, Michael A. Henning

Research output: Contribution to journalArticlepeer-review

9 Citations (Scopus)


Let G be a spanning subgraph of Ks,s and let H be the complement of G relative to Ks,s; that is, Ks,s = G ⊕ H is a factorization of Ks,s. The graph G is γ-critical relative to Ks,s if γ(G) = γand γ(G + e) = γ - 1 for all e ∈ E(H), where γ(G) denotes the domination number of G. We investigate γ-critical graphs for small values of γ. The 2-critical graphs and 3-critical graphs are characterized. A characterization of disconnected 4-critical graphs is presented. We show that the diameter of a connected 4-critical graph is at most 5 and that this bound is sharp. The diameter of a connected γ-critical graph, γ ≥ 4, is shown to be at most 3γ - 6.

Original languageEnglish
Pages (from-to)115-126
Number of pages12
JournalAustralasian Journal of Combinatorics
Publication statusPublished - 1998
Externally publishedYes

ASJC Scopus subject areas

  • Discrete Mathematics and Combinatorics


Dive into the research topics of 'Domination critical graphs with respect to relative complements'. Together they form a unique fingerprint.

Cite this