no. 5
A note on the double domination number in maximal outerplanar and planar graphs
RAIRO. Operations Research, Tome 56 (2022) no. 5, pp. 3367-3371

In a graph, a vertex dominates itself and its neighbors. A subset S of vertices of a graph G is a double dominating set of G if S dominates every vertex of G at least twice. The double domination number γ×2(G) of G is the minimum cardinality of a double dominating set of G. In this paper, we prove that the double domination number of a maximal outerplanar graph G of order n is bounded above by n+k 2, where k is the number of pairs of consecutive vertices of degree two and with distance at least 3 on the outer cycle. We also prove that γ ×2 (G)≤5n 8 for a Hamiltonian maximal planar graph G of order n ≥ 7.

DOI : 10.1051/ro/2022150
Classification : 05C69
Keywords: Domination, double domination, maximal outerplanar graph, Hamiltonian maximal planar graph 
@article{RO_2022__56_5_3367_0,
     author = {Abd Aziz, Noor A{\textquoteright}lawiah and Jafari Rad, Nader and Kamarulhaili, Hailiza},
     title = {A note on the double domination number in maximal outerplanar and planar graphs},
     journal = {RAIRO. Operations Research},
     pages = {3367--3371},
     year = {2022},
     publisher = {EDP-Sciences},
     volume = {56},
     number = {5},
     doi = {10.1051/ro/2022150},
     mrnumber = {4481127},
     zbl = {1502.05178},
     language = {en},
     url = {https://www.numdam.org/articles/10.1051/ro/2022150/}
}
TY  - JOUR
AU  - Abd Aziz, Noor A’lawiah
AU  - Jafari Rad, Nader
AU  - Kamarulhaili, Hailiza
TI  - A note on the double domination number in maximal outerplanar and planar graphs
JO  - RAIRO. Operations Research
PY  - 2022
SP  - 3367
EP  - 3371
VL  - 56
IS  - 5
PB  - EDP-Sciences
UR  - https://www.numdam.org/articles/10.1051/ro/2022150/
DO  - 10.1051/ro/2022150
LA  - en
ID  - RO_2022__56_5_3367_0
ER  - 
%0 Journal Article
%A Abd Aziz, Noor A’lawiah
%A Jafari Rad, Nader
%A Kamarulhaili, Hailiza
%T A note on the double domination number in maximal outerplanar and planar graphs
%J RAIRO. Operations Research
%D 2022
%P 3367-3371
%V 56
%N 5
%I EDP-Sciences
%U https://www.numdam.org/articles/10.1051/ro/2022150/
%R 10.1051/ro/2022150
%G en
%F RO_2022__56_5_3367_0
Abd Aziz, Noor A’lawiah; Jafari Rad, Nader; Kamarulhaili, Hailiza. A note on the double domination number in maximal outerplanar and planar graphs. RAIRO. Operations Research, Tome 56 (2022) no. 5, pp. 3367-3371. doi: 10.1051/ro/2022150

[1] M. Blidia, M. Chellali and T. W. Haynes, Characterizations of trees with equal paired and double domination numbers. Discrete Math. 306 (2006) 1840–1845. | MR | Zbl | DOI

[2] A. Cabrera Martínez and J. A. Rodríguez-Velázquez, A note on double domination in graphs. Preprint (2021). | arXiv | MR

[3] M. Dorfling, J. H. Hattingh and E. Jonck, Total domination in maximal outerplanar graphs. Discrete Appl. Math. 217 (2017) 506–511. | MR | Zbl | DOI

[4] J. Harant and M. A. Henning, On double domination in graphs. Discuss. Math. Graph Theory 25 (2005) 29–34. | MR | Zbl | DOI

[5] F. Harary and T. W. Haynes, Double domination in graphs. Ars Comb. 55 (2000) 201–213. | MR | Zbl

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

[7] T. W. Haynes, S. T. Hedetniemi and M. A. Henning, Topics in domination in graphs, In Vol. 64 of Developments in Mathematics, Springer, Cham (2020). | DOI

[8] M. A. Henning, Graphs with large double domination numbers. Discuss. Math. Graph Theory 25 (2005) 13–28. | MR | Zbl | DOI

[9] M. A. Henning and P. Kaemawichanurat, Semipaired domination in maximal outerplanar graphs. J. Comb. Optim. 38 (2019) 911–926. | MR | Zbl | DOI

[10] E. L. King and M. J. Pelsmajer, Dominating sets in plane triangulations. Discrete Math. 310 (2010) 2221–2230. | MR | Zbl | DOI

[11] M. Lemánska, R. Zuazua and P. Zylinski, Total dominating sets in maximal outerplanar graphs. Graphs Comb. 33 (2017) 991–998. | MR | Zbl | DOI

[12] Z. Li, E. Zhu, Z. Shao and J. Xu, On dominating sets of maximal outerplanar and planar graphs. Discrete Appl. Math. 198 (2016) 164–169. | MR | Zbl | DOI

[13] Ch Liu, A note on domination number in maximal outerplanar graphs. Discrete Appl. Math. 293 (2021) 90–94. | MR | Zbl | DOI

[14] L. R. Matheson and R. E. Tarjan, Dominating sets in planar graphs. Eur. J. Comb. 17 (1996) 565–568. | MR | Zbl | DOI

[15] Z. Shao, S. M. Sheikholeslami, M. Chellali, R. Khoeilar and H. Karami, A proof of a conjecture on the paired-domination subdivision number. Graphs Comb. 38 (2022) 1–13. | MR | Zbl | DOI

[16] Sh Tokunaga, Dominating sets of maximal outerplanar graphs. Discrete Appl. Math. 161 (2013) 3097–3099. | MR | Zbl | DOI

[17] H. Whitney, A theorem on graphs. Ann. Math. 32 (1931) 378–390. | MR | Zbl | DOI

[18] W. Zhuang, Double domination in maximal outerplanar graphs. Preprint (2021). | arXiv

Cité par Sources :