A tight bound for independent domination of cubic graphs without 4‐cycles

DOI10.1002/JGT.22968MaRDI QIDQ6094034zbMATH OpenOpenAlexFDO

Authors Eun-Kyung Cho, Ilkyoo Choi, Hyemin Kwon, Boram Park

Publication date 9 October 2023

Published in Journal of Graph Theory (Search for Journal in Brave)

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

zbMATH Keywords

domination numbercubic graphregular graphindependent domination number

Mathematics Subject Classification ID

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

Abstract: Given a graph $G$, a dominating set of $G$ is a set $S$ of vertices such that each vertex not in $S$ has a neighbor in $S$. The domination number of $G$, denoted $gamma(G)$, is the minimum size of a dominating set of $G$. The independent domination number of $G$, denoted $i(G)$, is the minimum size of a dominating set of $G$ that is also independent. Recently, Abrishami and Henning proved that if $G$ is a cubic graph with girth at least $6$, then $i(G)lefrac411|V(G)|$. We show a result that not only improves upon the upper bound of the aforementioned result, but also applies to a larger class of graphs, and is also tight. Namely, we prove that if $G$ is a cubic graph without $4$-cycles, then $i(G)lefrac514|V(G)|$, which is tight. Our result also implies that every cubic graph $G$ without $4$-cycles satisfies $fraci(G)gamma(G)lefrac54$, which partially answers a question by O and West in the affirmative.

Recommendations

• Domination versus independent domination in cubic graphs
• Independent domination in cubic graphs
• Independent domination in subcubic graphs
• Independent domination in subcubic graphs of girth at least six
• An improved upper bound on the independent domination number in cubic graphs of girth at least six

Cites work

• scientific article; zbMATH DE number 3159208 (Why is no real title available?)
• scientific article; zbMATH DE number 3172309 (Why is no real title available?)
• An improved upper bound on the independent domination number in cubic graphs of girth at least six
• An introduction to the discharging method via graph coloring
• Cubic graphs with large ratio of independent domination number to domination number
• Independent dominating sets in graphs of girth five
• Independent domination in cubic graphs
• Independent domination in graphs: A survey and recent results
• Independent domination in subcubic bipartite graphs of girth at least six
• Independent domination in subcubic graphs of girth at least six
• Independent sets in regular graphs
• Linear programming and the worst-case analysis of greedy algorithms on cubic graphs
• On independent domination number of regular graphs
• On independent domination of regular graphs
• On the independent domination number of regular graphs

Cited in

(4)

• An improved upper bound on the independent domination number in cubic graphs of girth at least six
• Independent domination versus packing in subcubic graphs
• A note on the \(P_3\)-isolation number of a graph
• A note on the dominating circuit conjecture and subgraphs of essentially 4-edge-connected cubic graphs

This page was built for publication: A tight bound for independent domination of cubic graphs without 4‐cycles

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