Mathematica Bohemica

Mathematica Bohemica, Vol. 148, No. 4, pp. 555-560, 2023

On the domination of triangulated discs

Noor A'lawiah Abd Aziz, Nader Jafari Rad, Hailiza Kamarulhaili

Received August 10, 2021. Published online December 5, 2022.

Abstract: 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 $\frac14(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.

Keywords: domination; double domination; total domination; double total domination; planar graph; triangulated disc

Classification MSC: 05C69

DOI: 10.21136/MB.2022.0122-21

PDF available at: Institute of Mathematics CAS

References:
[1] S. Bermudo, J. L. Sanchéz, J. M. Sigarreta: 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] M. Blidia, M. Chellali, T. W. Haynes: 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] A. Cabrera-Martínez: 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] A. Cabrera-Martínez, J. A. Rodríguez-Velázquez: 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] C. N. Campos, Y. Wakabayashi: 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] H. Fernau, J. A. Rodríguez-Velázquez, J. M. Sigarreta: Global powerful $r$-alliances and total $k$-domination in graphs. Util. Math. 98 (2015), 127-147. MR 3410888 | Zbl 1343.05115
[7] J. Harant, M. A. Henning: On double domination in graphs. Discuss. Math., Graph Theory 25 (2005), 29-34. DOI 10.7151/dmgt.1256 | MR 2152046 | Zbl 1073.05049
[8] F. Harary, T. W. Haynes: Double domination in graphs. Ars Comb. 55 (2000), 201-213. MR 1755232 | Zbl 0993.05104
[9] T. W. Haynes, S. T. Hedetniemi, P. J. Slater: 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] M. A. Henning, N. Jafari Rad: 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] M. A. Henning, A. P. Kazemi: $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] M. A. Henning, A. Yeo: 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] E. L. C. King, M. J. Pelsmajer: 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] Z. Li, E. Zhu, Z. Shao, J. Xu: 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] L. R. Matheson, R. E. Tarjan: Dominating sets in planar graphs. Eur. J. Comb. 17 (1996), 565-568. DOI 10.1006/eujc.1996.0048 | MR 1401911 | Zbl 0862.05032
[16] D. Pradhan: 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] S. Tokunaga: 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] S. Tokunaga: On domination number of triangulated discs. J. Inf. Process. 28 (2020), 846-848. DOI 10.2197/ipsjjip.28.846

Affiliations: Noor A'lawiah Abd Aziz, School of Mathematical Sciences, Universiti Sains Malaysia, 11800 USM Penang, Malaysia, e-mail: nooralawiah@gmail.com; Nader Jafari Rad (corresponding author), Department of Mathematics, Shahed University, Tehran, Iran, e-mail: n.jafarirad@gmail.com; Hailiza Kamarulhaili, School of Mathematical Sciences, Universiti Sains Malaysia, 11800 USM Penang, Malaysia, e-mail: hailiza@usm.my

[List of online first articles] [Contents of Mathematica Bohemica] [Full text of the older issues of Mathematica Bohemica at DML-CZ]

PDF available at:

Institute of Mathematics CAS
free access