A characterization of domination 4-relative-critical graphs of diameter 5

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.