Geodesic
On Independent Domination in Planar Cubic Graphs
Discussiones Mathematicae. Graph Theory, Tome 39 (2019) no. 4, pp. 841-853.

Voir la notice de l'article provenant de la source Library of Science

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 □ K_2 } is a connected, cubic graph on n vertices, then i(G) ≤ 3/8 n, where C_5 □ 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) ≤ 1/3 n, and we provide an infinite family of such graphs that achieve this bound.
Keywords: independent domination number, domination number, cubic graphs 
@article{DMGT_2019_39_4_a5,
     author = {Abrishami, Gholamreza and Henning, Michael A. and Rahbarnia, Freydoon},
     title = {On {Independent} {Domination} in {Planar} {Cubic} {Graphs}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {841--853},
     publisher = {mathdoc},
     volume = {39},
     number = {4},
     year = {2019},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2019_39_4_a5/}
}
TY  - JOUR
AU  - Abrishami, Gholamreza
AU  - Henning, Michael A.
AU  - Rahbarnia, Freydoon
TI  - On Independent Domination in Planar Cubic Graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2019
SP  - 841
EP  - 853
VL  - 39
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2019_39_4_a5/
LA  - en
ID  - DMGT_2019_39_4_a5
ER  - 
%0 Journal Article
%A Abrishami, Gholamreza
%A Henning, Michael A.
%A Rahbarnia, Freydoon
%T On Independent Domination in Planar Cubic Graphs
%J Discussiones Mathematicae. Graph Theory
%D 2019
%P 841-853
%V 39
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2019_39_4_a5/
%G en
%F DMGT_2019_39_4_a5
Abrishami, Gholamreza; Henning, Michael A.; Rahbarnia, Freydoon. On Independent Domination in Planar Cubic Graphs. Discussiones Mathematicae. Graph Theory, Tome 39 (2019) no. 4, pp. 841-853. http://geodesic.mathdoc.fr/item/DMGT_2019_39_4_a5/

[1] C. Barefoot, F. Harary and K.F. Jones, What is the difference between the domi- nation and independent domination numbers of a cubic graph?, Graphs Combin. 7 (1991) 205–208. doi:10.1007/BF01788145

[2] P. Dorbec, M.A. Henning, M. Montassier and J. Southey, Independent domination in cubic graphs, J. Graph Theory 80 (2015) 329–349. doi:10.1002/jgt.21855

[3] W. Goddard and M.A. Henning, Independent domination in graphs: A survey and recent results, Discrete Math. 313 (2013) 839–854. doi:10.1016/j.disc.2012.11.031

[4] W. Goddard, M. A. Henning, J. Lyle and J. Southey, On the independent domination number of regular graphs, Ann. Comb. 16 (2012) 719–732. doi:10.1007/s00026-012-0155-4

[5] W. Goddard and J. Lyle, Independent dominating sets in triangle-free graphs, J. Comb. Optim. 23 (2012) 9–20. doi:10.1007/s10878-010-9336-4

[6] T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Fundamentals of Domination in Graphs (Marcel Dekker, Inc. New York, 1998).

[7] M.A. Henning, C. Löwenstein and D. Rautenbach, Independent domination in sub- cubic bipartite graphs of girth at least six, Discrete Appl. Math. 162 (2014) 399–403. doi:10.1016/j.dam.2013.08.035

[8] A.V. Kostochka, The independent domination number of a cubic 3 -connected graph can be much larger than its domination number, Graphs Combin. 9 (1993) 235–237. doi:10.1007/BF02988312

[9] P.C.B. Lam, W.C. Shiu and L. Sun, On independent domination number of regular graphs, Discrete Math. 202 (1999) 135–144. doi:10.1016/S0012-365X(98)00350-1

[10] J. Lyle, A note on independent sets in graphs with large minimum degree and small cliques, Electron. J. Combin. 21 (2014) #P2.38.

[11] O. Ore, Theory of graphs, Amer. Math. Soc. Transl. 38 (1962) 206–212. doi:10.1090/coll/038

[12] J. Southey and M.A. Henning, Domination versus independent domination in cubic graphs, Discrete Math. 313 (2013) 1212–1220. doi:10.1016/j.disc.2012.01.003

[13] T. Zhu and B. Wu, Domination of maximal K4-minor free graphs and maximal K2,3-minor free graphs, and disproofs of two conjectures on planar graphs, Discrete Appl. Math. 194 (2015) 147–153. doi:10.1016/j.dam.2015.05.029