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

DOI10.1002/JGT.22968zbMATH Open1522.05354arXiv2112.11720OpenAlexW4367680209MaRDI QIDQ6094034FDOQ6094034

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)

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.

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

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

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)

Cites Work

• Independent domination in graphs: A survey and recent results
• Title not available (Why is that?)
• Title not available (Why is that?)
• On independent domination number of regular graphs
• On the independent domination number of regular graphs
• Cubic graphs with large ratio of independent domination number to domination number
• Independent domination in cubic graphs
• Independent sets in regular graphs
• Linear programming and the worst-case analysis of greedy algorithms on cubic graphs
• An introduction to the discharging method via graph coloring
• Independent domination in subcubic bipartite graphs of girth at least six
• On independent domination of regular 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
• Independent dominating sets in graphs of girth five

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)