Back to Search Start Over

Tight bound for independent domination of cubic graphs without $4$-cycles

Authors :
Cho, Eun-Kyung
Choi, Ilkyoo
Kwon, Hyemin
Park, Boram
Source :
J. Graph Theory 104.2 (2023) 372-386
Publication Year :
2021

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) \le \frac{4}{11}|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) \le \frac{5}{14}|V(G)|$, which is tight. Our result also implies that every cubic graph $G$ without $4$-cycles satisfies $\frac{i(G)}{\gamma(G)} \le \frac{5}{4}$, which partially answers a question by O and West in the affirmative.<br />Comment: 16 pages, 4 figures

Subjects

Subjects :
Mathematics - Combinatorics
05C69

Details

Database :
arXiv
Journal :
J. Graph Theory 104.2 (2023) 372-386
Publication Type :
Report
Accession number :
edsarx.2112.11720
Document Type :
Working Paper
Full Text :
https://doi.org/10.1002/jgt.22968