2019/07/12 by Elliot Krop, Jessica McDonald, Gregory J. Puleo
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics #Complexity and Algorithms in Graphs #Computer science #Domination analysis #Geometry #Graph #Inverse #Limits and Structures in Graph Theory #Mathematics #Upper and lower bounds #Vertex (graph theory) #cs.DM #math.CO #msc:05C69
paper · pdf · doi:10.20429/tag.2021.080205
published as Theory and Applications of Graphs, 8(2): Article 5, (2021) · 9 pages
arxiv created 2019/07/12 · openalex publication_date 2021/01/01 · arxiv updated 2021/11/15 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/31
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.