Upper bounds for inverse domination in graphs

DOI10.20429/TAG.2021.080205zbMATH Open1484.05159arXiv1907.05966OpenAlexW3193838004MaRDI QIDQ3380407FDOQ3380407

Authors: Elliot Krop, Jessica McDonald, Gregory J. Puleo 

Publication date: 28 September 2021

Published in: Theory and Applications of Graphs (Search for Journal in Brave)

Abstract: In any graph $G$, the domination number $gamma(G)$ is at most the independence number $alpha(G)$. The Inverse Domination Conjecture says that, in any isolate-free $G$, there exists pair of vertex-disjoint dominating sets $D,D^{\prime }$ with $|D|=gamma(G)$ and $|D^{\prime }|leqalpha(G)$. Here we prove that this statement is true if the upper bound $alpha(G)$ is replaced by $frac32alpha(G)-1$ (and $G$ is not a clique). We also prove that the conjecture holds whenever $gamma(G)leq5$ or $|V(G)|leq16$.

Full work available at URL: https://arxiv.org/abs/1907.05966

Recommendations

• On a conjecture about inverse domination in graphs.
• Some results related to the Kulli-Sigarkanti conjecture
• Inverse domination in graphs
• On \(n\)-inverse domination number in graphs
• Inverse total domination in graphs
• scientific article; zbMATH DE number 2192114
• scientific article; zbMATH DE number 6277684
• INVERSE DOMINATION AND INVERSE TOTAL DOMINATION FOR AN UNDIRECTED GRAPH
• Fractional inverse and inverse fractional domination.
• An algorithm for the inverse distance-2 dominating set of a graph

zbMATH Keywords

domination numberdominating setinverse dominating set, inverse domination numberinverse domination conjecture

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Cited In (10)

• My favorite domination conjectures in graph theory are bounded
• On a problem of Domke, Dunbar, Haynes, Hedetniemi, and Markus concerning the inverse domination number
• Some results related to the Kulli-Sigarkanti conjecture
• Some bounds on the size of DI-pathological graphs
• New parameter of inverse domination in graphs
• On a conjecture about inverse domination in graphs.
• On dominating graph of graphs, median graphs, partial cubes and complement of minimal dominating sets
• Title not available (Why is that?)
• On disjoint maximum and maximal independent sets in graphs and inverse independence number
• Fractional inverse and inverse fractional domination.

This page was built for publication: Upper bounds for inverse domination in graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3380407)