Independent Domination in Cubic Graphs

Paul Dorbec, Michael A. Henning, Mickael Montassier, Justin Southey

Research output: Contribution to journalArticlepeer-review

16 Citations (Scopus)


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 i(G), is the minimum cardinality of an independent dominating set. In this article, we show that if G≠C5□K2 is a connected cubic graph of order n that does not have a subgraph isomorphic to K2, □ 3, then i(G)≤3n/8. 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 γ(G)≤3n/8, where γ(G) denotes the domination number of G.

Original languageEnglish
Pages (from-to)329-349
Number of pages21
JournalJournal of Graph Theory
Issue number4
Publication statusPublished - Dec 2015


  • cubic graphs 05C69
  • domination number
  • independent domination number

ASJC Scopus subject areas

  • Geometry and Topology
  • Discrete Mathematics and Combinatorics


Dive into the research topics of 'Independent Domination in Cubic Graphs'. Together they form a unique fingerprint.

Cite this