Back to Search
Start Over
Tight bound for independent domination of cubic graphs without $4$-cycles
- 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 :
- Mathematics - Combinatorics
05C69
Subjects
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