Total Domination Critical Graphs With Respect to Relative Complements

Document Type


Publication Date



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.

This document is currently not available here.