Domination critical graphs with respect to relative complements

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 γ-critical relative to K_s,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.