Domination Critical Graphs With Respect to Relative Complements
Document Type
Article
Publication Date
12-1-1998
Description
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.
Citation Information
Haynes, Teresa W.; and Henning, Michael A.. 1998. Domination Critical Graphs With Respect to Relative Complements. Australasian Journal of Combinatorics. Vol.18 115-126. https://ajc.maths.uq.edu.au/pdf/18/ocr-ajc-v18-p115.pdf ISSN: 1034-4942