On Independent Domination in Planar Cubic Graphs

Gholamreza Abrishami, Michael A. Henning, Freydoon Rahbarnia

Research output: Contribution to journalArticlepeer-review

5 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, i(G), of G is the minimum cardinality of an independent dominating set. Goddard and Henning [Discrete Math. 313 (2013) 839-854] posed the conjecture that if G ϵ {K3,3, C5 □ K2} is a connected, cubic graph on n vertices, then i(G)≤38n $i\left( G \right) \le {3 \over 8}n$ , where C5 □ K2 is the 5-prism. As an application of known result, we observe that this conjecture is true when G is 2-connected and planar, and we provide an infinite family of such graphs that achieve the bound. We conjecture that if G is a bipartite, planar, cubic graph of order n, then i(G)≤13n $i\left( G \right) \le {1 \over 3}n$ , and we provide an infinite family of such graphs that achieve this bound.

Original languageEnglish
Pages (from-to)841-853
Number of pages13
JournalDiscussiones Mathematicae - Graph Theory
Issue number4
Publication statusPublished - 1 Nov 2019


  • cubic graphs
  • domination number
  • independent domination number

ASJC Scopus subject areas

  • Discrete Mathematics and Combinatorics
  • Applied Mathematics


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

Cite this