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

被引:4
作者
Cho, Eun-Kyung [1 ]
Choi, Ilkyoo [1 ]
Kwon, Hyemin [2 ]
Park, Boram [2 ]
机构
[1] Hankuk Univ Foreign Studies, Dept Math, Yongin, Gyeonggi Do, South Korea
[2] Ajou Univ, Dept Math, Suwon, Gyeonggi Do, South Korea
基金
新加坡国家研究基金会;
关键词
cubic graph; domination number; independent domination number; regular graph; NUMBER; GIRTH; SETS;
D O I
10.1002/jgt.22968
中图分类号
O1 [数学];
学科分类号
0701 ; 070101 ;
摘要
Given a graph G $G$, a dominating set of G $G$ is a set S $S$ of vertices such that each vertex not in S $S$ has a neighbor in S $S$. Let gamma(G) $\gamma (G)$ denote the minimum size of a dominating set of G $G$. The independent domination number of G $G$, denoted i(G) $i(G)$, is the minimum size of a dominating set of G $G$ that is also independent. We prove that if G $G$ is a cubic graph without 4-cycles, then i(G)<= 514 divide V(G) divide $i(G)\le \frac{5}{14}| V(G)| $, and the bound is tight. This result improves upon two results from two papers by Abrishami and Henning. Our result also implies that every cubic graph G $G$ without 4-cycles satisfies i(G)gamma(G)<= 54 $\frac{i(G)}{\gamma (G)}\le \frac{5}{4}$, which supports a question asked by O and West.
引用
收藏
页码:372 / 386
页数:15
相关论文
共 15 条
[1]   An Improved Upper Bound on the Independent Domination Number in Cubic Graphs of Girth at Least Six [J].
Abrishami, Gholamreza ;
Henning, Michael A. .
GRAPHS AND COMBINATORICS, 2022, 38 (02)
[2]   Independent domination in subcubic graphs of girth at least six [J].
Abrishami, Gholamreza ;
Henning, Michael A. .
DISCRETE MATHEMATICS, 2018, 341 (01) :155-164
[3]  
Berge C., 1962, Theory of Graphs and Its Applications
[4]  
CHO E, 2023, ADV POLYM SCI, V103, P159
[5]   An introduction to the discharging method via graph coloring [J].
Cranston, Daniel W. ;
West, Douglas B. .
DISCRETE MATHEMATICS, 2017, 340 (04) :766-793
[6]   Independent Domination in Cubic Graphs [J].
Dorbec, Paul ;
Henning, Michael A. ;
Montassier, Mickael ;
Southey, Justin .
JOURNAL OF GRAPH THEORY, 2015, 80 (04) :329-349
[7]  
Duckworth W, 2010, ELECTRON J COMB, V17
[8]   Independent domination in graphs: A survey and recent results [J].
Goddard, Wayne ;
Henning, Michael A. .
DISCRETE MATHEMATICS, 2013, 313 (07) :839-854
[9]   On the Independent Domination Number of Regular Graphs [J].
Goddard, Wayne ;
Henning, Michael A. ;
Lyle, Jeremy ;
Southey, Justin .
ANNALS OF COMBINATORICS, 2012, 16 (04) :719-732
[10]   Independent dominating sets in graphs of girth five [J].
Harutyunyan, Ararat ;
Horn, Paul ;
Verstraete, Jacques .
COMBINATORICS PROBABILITY AND COMPUTING, 2021, 30 (03) :344-359