Upper bounds for inverse domination in graphs

DOI10.20429/TAG.2021.080205MaRDI QIDQ3380407zbMATH OpenOpenAlexFDO

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)

Copyright license Creative Commons Attribution 4.0 International

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

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)

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$.

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

Cited in

(10)

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

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)