A Characterization of Domination 4-Relative-Critical Graphs of Diameter 5
Document Type
Article
Publication Date
12-1-2000
Description
Let G be a spanning subgraph of K(s, s) and let H be the complement of G relative to K(s, s); that is, K(s, s) = G⊕H is a factorization of K(s, s). The graph G is,),-relative-critical if γ(G) = γ and γ(G + e) = γ - 1 for all e ∈ E(H), where γ(G) denotes the domination number of G. The 2-relative-critical graphs and 3-relative-critical graphs are characterized in [7]. In [7], it is shown that the diameter of a connected 4-relativecritical graph is at most 5. In this paper, we construct five families of connected 4-relative-critical graphs of diameter 5 and show that a graph G is a connected 4-relative-critical graph of diameter 5 if and only if G belongs to one of these five families.
Citation Information
Haynes, Teresa W.; and Henning, Michael A.. 2000. A Characterization of Domination 4-Relative-Critical Graphs of Diameter 5. Australasian Journal of Combinatorics. Vol.22 19-36. https://ajc.maths.uq.edu.au/pdf/22/ocr-ajc-v22-p19.pdf ISSN: 1034-4942