Upper bounds for inverse domination in graphs

07/12/2019
by   Elliot Krop, et al.
0

In any graph G, the domination number γ(G) is at most the independence number α(G). The Inverse Domination Conjecture says that, in any isolate-free G, there exists pair of vertex-disjoint dominating sets D, D' with |D|=γ(G) and |D'| ≤α(G). Here we prove that this statement is true if the upper bound α(G) is replaced by 3/2α(G) - 1 (and G is not a clique). We also prove that the conjecture holds whenever γ(G)≤ 5 or |V(G)|≤ 16.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset