Independent Domination in Claw-Free Cubic Graphs
Authors:
Open Access
- 22 August 2024
- journal article
- Published by Scilight Press Pty Ltd in Applied Mathematics and Statistics
- Vol. 1 (1) , 3
Abstract
Article Linyu Li 1 and Jun Yue 2,* 1 School of Mathematics and Statistics, Shandong Normal University, Jinan 250358, China 2 School of Mathematics Science, Tiangong University, Tianjin 300387, China * Correspondence: yuejun06@126.com Received: 7 June 2024; Revised: 5 August 2024; Accepted: 13 August 2024; Published: 22 August 2024 Abstract: A vertex set S of a graph G is called an independent dominating set if S is an independent set and each vertex in V(G)\S is adjacent to a vertex in S. The independent domination number i(G) of G is the minimum cardinality of an independent dominating set in G. This paper first proves that if G is a connected \(K_{1,3}\) -free cubic graph, then \(i(G)\leq \frac{1}{3}|V(G)|\) . Meanwhile, \(i(G)=\frac{1}{3}|V(G)|\) if and only if \(G\in \mathcal{H}\) , where \(\mathcal{H}\) is an infinite cubic family with each graph being a \(C_6^+\) -necklace. Then, it is shown that if G is a \(\{K_{1,3}, K_4^-, C_6^+\}\) -free cubic graph with no \(C_3\Box K_2\) -component, then \(i(G)\leq \frac{5}{18}|V(G)|\) . This result is tight.
Keywords
This publication has 9 references indexed in Scilit:
- Independent Domination in Claw-Free Cubic GraphsApplied Mathematics and Statistics, 2024
- Independent Domination in Cubic GraphsJournal of Graph Theory, 2015
- Independent domination in subcubic bipartite graphs of girth at least sixDiscrete Applied Mathematics, 2014
- Domination versus independent domination in cubic graphsDiscrete Mathematics, 2013
- Independent domination in graphs: A survey and recent resultsDiscrete Mathematics, 2013
- On the Independent Domination Number of Regular GraphsAnnals of Combinatorics, 2012
- Independent dominating sets in triangle-free graphsJournal of Combinatorial Optimization, 2010
- On independent domination number of regular graphsDiscrete Mathematics, 1999
- Independent sets in regular graphsIsrael Journal of Mathematics, 1964