Total domination critical graphs with respect to relative complements.
Teresa W. Haynes, Michael A. Henning, Lucas C. van der Merwe · Digital Commons - East Tennessee State University (East Tennessee State University) · 2002
A set S of vertices of a graph G is a total dominating set if every vertex of V(G) is adjacent to some vertex in S. The total domination number γt(G) is the minimum cardinality of a total dominating set of G. 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 kt-critical relative to Ks,s if γt(G) = k and γ t(G + e) < k for all e ∈ E(H). We study k t-critical graphs relative to Ks,s for small values of k. In particular, we characterize the 3t-critical and 4 t-critical graphs.