Authors: G. Abrishami, M.A. Henning, F. Rahbarnia Title: On independent domination in planar, cubic graphs Source: Discussiones Mathematicae Graph Theory Received 02.08.2017, Revised 01.12.2017, Accepted 01.12.2017, doi: 10.7151/dmgt.2105 | |
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, 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 ∉ {K_{3,3}, C_{5} \, \Box \, K_{2}} is a connected, cubic graph on n vertices, then i(G) \le \frac{3}{8}n, where C_{5} \, \Box \, K_{2} 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) \le \frac{1}{3}n, and we provide an infinite family of such graphs that achieve this bound. | |
Keywords: independent domination number, domination number, cubic graphs | |
Links: |