Article
Full entry |
PDF
(0.1 MB)
Feedback
PDF
(0.1 MB)
Feedback
Keywords:
domination; double domination; total domination; double total domination; planar graph; triangulated disc
domination; double domination; total domination; double total domination; planar graph; triangulated disc
Summary:
Let $G$ be a $3$-connected triangulated disc of order $n$ with the boundary cycle $C$ of the outer face of $G$. Tokunaga (2013) conjectured that $G$ has a dominating set of cardinality at most $\frac 14(n+2)$. This conjecture is proved in Tokunaga (2020) for $G-C$ being a tree. In this paper we prove the above conjecture for $G-C$ being a unicyclic graph. We also deduce some bounds for the double domination number, total domination number and double total domination number in triangulated discs.
References:
[1] Bermudo, S., Sanchéz, J. L., Sigarreta, J. M.: Total $k$-domination in Cartesian product graphs. Period. Math. Hung. 75 (2017), 255-267. DOI 10.1007/s10998-017-0191-2 | MR 3718519 | Zbl 1413.05279
[2] Blidia, M., Chellali, M., Haynes, T. W.: Characterizations of trees with equal paired and double domination numbers. Discrete Math. 306 (2006), 1840-1845. DOI 10.1016/j.disc.2006.03.061 | MR 2251565 | Zbl 1100.05068
[3] Cabrera-Martínez, A.: New bounds on the double domination number of trees. Discrete Appl. Math. 315 (2022), 97-103. DOI 10.1016/j.dam.2022.03.022 | MR 4407663 | Zbl 07516299
[4] Cabrera-Martínez, A., Rodríguez-Velázquez, J. A.: A note on double domination in graphs. Discrete Appl. Math. 300 (2021), 107-111. DOI 10.1016/j.dam.2021.05.011 | MR 4264160 | Zbl 1465.05124
[5] Campos, C. N., Wakabayashi, Y.: On dominating sets of maximal outerplanar graphs. Discrete Appl. Math. 161 (2013), 330-335. DOI 10.1016/j.dam.2012.08.023 | MR 2998434 | Zbl 1254.05136
[6] Fernau, H., Rodríguez-Velázquez, J. A., Sigarreta, J. M.: Global powerful $r$-alliances and total $k$-domination in graphs. Util. Math. 98 (2015), 127-147. MR 3410888 | Zbl 1343.05115
[7] Harant, J., Henning, M. A.: On double domination in graphs. Discuss. Math., Graph Theory 25 (2005), 29-34. DOI 10.7151/dmgt.1256 | MR 2152046 | Zbl 1073.05049
[8] Harary, F., Haynes, T. W.: Double domination in graphs. Ars Comb. 55 (2000), 201-213. MR 1755232 | Zbl 0993.05104
[9] Haynes, T. W., Hedetniemi, S. T., Slater, P. J.: Fundamentals of Domination in Graphs. Pure and Applied Mathematics, Marcel Dekker 208. Marcel Dekker, New York (1998). DOI 10.1201/9781482246582 | MR 1605684 | Zbl 0890.05002
[10] Henning, M. A., Rad, N. Jafari: Upper bounds on the $k$-tuple (Roman) domination number of a graph. Graphs Comb. 37 (2021), 325-336. DOI 10.1007/s00373-020-02249-7 | MR 4197383 | Zbl 1459.05239
[11] Henning, M. A., Kazemi, A. P.: $k$-tuple total domination in graphs. Discrete Appl. Math. 158 (2010), 1006-1011. DOI 10.1016/j.dam.2010.01.009 | MR 2607047 | Zbl 1210.05097
[12] Henning, M. A., Yeo, A.: Strong transversals in hypergraphs and double total domination in graphs. SIAM J. Discrete Math. 24 (2010), 1336-1355. DOI 10.1137/090777001 | MR 2735927 | Zbl 1221.05254
[13] King, E. L. C., Pelsmajer, M. J.: Dominating sets in plane triangulations. Discrete Math. 310 (2010), 2221-2230. DOI 10.1016/j.disc.2010.03.022 | MR 2659172 | Zbl 1203.05120
[14] Li, Z., Zhu, E., Shao, Z., Xu, J.: On dominating sets of maximal outerplanar and planar graphs. Discrete Appl. Math. 198 (2016), 164-169. DOI 10.1016/j.dam.2015.06.024 | MR 3426889 | Zbl 1327.05263
[15] Matheson, L. R., Tarjan, R. E.: Dominating sets in planar graphs. Eur. J. Comb. 17 (1996), 565-568. DOI 10.1006/eujc.1996.0048 | MR 1401911 | Zbl 0862.05032
[16] Pradhan, D.: Algorithmic aspects of $k$-tuple total domination in graphs. Inf. Process. Lett. 112 (2012), 816-822. DOI 10.1016/j.ipl.2012.07.010 | MR 2960327 | Zbl 1248.68222
[17] Tokunaga, S.: Dominating sets of maximal outerplanar graphs. Discrete Appl. Math. 161 (2013), 3097-3099. DOI 10.1016/j.dam.2013.06.025 | MR 3126677 | Zbl 1287.05109
[18] Tokunaga, S.: On domination number of triangulated discs. J. Inf. Process. 28 (2020), 846-848. DOI 10.2197/ipsjjip.28.846
Search
Partner of
