Independent Domination in Cubic Graphs

Abstract : A set S of vertices in a graph G is an independent dominating set of G if S is an independent set and every vertex not in S is adjacent to a vertex in S. The independent domination number of G, denoted by inline image, is the minimum cardinality of an independent dominating set. In this article, we show that if inline image is a connected cubic graph of order n that does not have a subgraph isomorphic to K2, 3, then inline image. As a consequence of our main result, we deduce Reed's important result [Combin Probab Comput 5 (1996), 277–295] that if G is a cubic graph of order n, then inline image, where inline image denotes the domination number of G.
Type de document :
Article dans une revue
Journal of Graph Theory, Wiley, 2015, 80 (4), pp.329-349. 〈10.1002/jgt.21855〉
Liste complète des métadonnées

https://hal-lirmm.ccsd.cnrs.fr/lirmm-01263782
Contributeur : Mickael Montassier <>
Soumis le : jeudi 28 janvier 2016 - 11:27:48
Dernière modification le : vendredi 20 avril 2018 - 12:00:03

Identifiants

Citation

Paul Dorbec, Michael A. Henning, Mickaël Montassier, Justin Southey. Independent Domination in Cubic Graphs. Journal of Graph Theory, Wiley, 2015, 80 (4), pp.329-349. 〈10.1002/jgt.21855〉. 〈lirmm-01263782〉

Partager

Métriques

Consultations de la notice

96