Domination and total domination critical trees 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) · 2001
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. For a graphical parameter μ(G), a graph G is μ(G)-critical if μ(G + e) < μ(G) for every e in the ordinary complement Ḡ of G, while G is μ(G)-critical relative to Ks,s if μ(G + e) < μ(G) for all e ∈ E(H) We show that no tree T is μ(T)-critical and characterize the trees T that are μ(T)-critical relative to Ks,s, where μ(T) is the domination number and the total domination number of T.