| Title:
|
On the domination of triangulated discs (English) |
| Author:
|
Abd Aziz, Noor A'lawiah |
| Author:
|
Jafari Rad, Nader |
| Author:
|
Kamarulhaili, Hailiza |
| Language:
|
English |
| Journal:
|
Mathematica Bohemica |
| ISSN:
|
0862-7959 (print) |
| ISSN:
|
2464-7136 (online) |
| Volume:
|
148 |
| Issue:
|
4 |
| Year:
|
2023 |
| Pages:
|
555-560 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| 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. (English) |
| Keyword:
|
domination |
| Keyword:
|
double domination |
| Keyword:
|
total domination |
| Keyword:
|
double total domination |
| Keyword:
|
planar graph |
| Keyword:
|
triangulated disc |
| MSC:
|
05C69 |
| idZBL:
|
Zbl 07790603 |
| idMR:
|
MR4673837 |
| DOI:
|
10.21136/MB.2022.0122-21 |
| . |
| Date available:
|
2023-11-23T12:38:54Z |
| Last updated:
|
2024-12-13 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/151974 |
| . |
| Reference:
|
[1] Bermudo, S., Sanchéz, J. L., Sigarreta, J. M.: Total $k$-domination in Cartesian product graphs.Period. Math. Hung. 75 (2017), 255-267. Zbl 1413.05279, MR 3718519, 10.1007/s10998-017-0191-2 |
| Reference:
|
[2] Blidia, M., Chellali, M., Haynes, T. W.: Characterizations of trees with equal paired and double domination numbers.Discrete Math. 306 (2006), 1840-1845. Zbl 1100.05068, MR 2251565, 10.1016/j.disc.2006.03.061 |
| Reference:
|
[3] Cabrera-Martínez, A.: New bounds on the double domination number of trees.Discrete Appl. Math. 315 (2022), 97-103. Zbl 07516299, MR 4407663, 10.1016/j.dam.2022.03.022 |
| Reference:
|
[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. Zbl 1465.05124, MR 4264160, 10.1016/j.dam.2021.05.011 |
| Reference:
|
[5] Campos, C. N., Wakabayashi, Y.: On dominating sets of maximal outerplanar graphs.Discrete Appl. Math. 161 (2013), 330-335. Zbl 1254.05136, MR 2998434, 10.1016/j.dam.2012.08.023 |
| Reference:
|
[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. Zbl 1343.05115, MR 3410888 |
| Reference:
|
[7] Harant, J., Henning, M. A.: On double domination in graphs.Discuss. Math., Graph Theory 25 (2005), 29-34. Zbl 1073.05049, MR 2152046, 10.7151/dmgt.1256 |
| Reference:
|
[8] Harary, F., Haynes, T. W.: Double domination in graphs.Ars Comb. 55 (2000), 201-213. Zbl 0993.05104, MR 1755232 |
| Reference:
|
[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). Zbl 0890.05002, MR 1605684, 10.1201/9781482246582 |
| Reference:
|
[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. Zbl 1459.05239, MR 4197383, 10.1007/s00373-020-02249-7 |
| Reference:
|
[11] Henning, M. A., Kazemi, A. P.: $k$-tuple total domination in graphs.Discrete Appl. Math. 158 (2010), 1006-1011. Zbl 1210.05097, MR 2607047, 10.1016/j.dam.2010.01.009 |
| Reference:
|
[12] Henning, M. A., Yeo, A.: Strong transversals in hypergraphs and double total domination in graphs.SIAM J. Discrete Math. 24 (2010), 1336-1355. Zbl 1221.05254, MR 2735927, 10.1137/090777001 |
| Reference:
|
[13] King, E. L. C., Pelsmajer, M. J.: Dominating sets in plane triangulations.Discrete Math. 310 (2010), 2221-2230. Zbl 1203.05120, MR 2659172, 10.1016/j.disc.2010.03.022 |
| Reference:
|
[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. Zbl 1327.05263, MR 3426889, 10.1016/j.dam.2015.06.024 |
| Reference:
|
[15] Matheson, L. R., Tarjan, R. E.: Dominating sets in planar graphs.Eur. J. Comb. 17 (1996), 565-568. Zbl 0862.05032, MR 1401911, 10.1006/eujc.1996.0048 |
| Reference:
|
[16] Pradhan, D.: Algorithmic aspects of $k$-tuple total domination in graphs.Inf. Process. Lett. 112 (2012), 816-822. Zbl 1248.68222, MR 2960327, 10.1016/j.ipl.2012.07.010 |
| Reference:
|
[17] Tokunaga, S.: Dominating sets of maximal outerplanar graphs.Discrete Appl. Math. 161 (2013), 3097-3099. Zbl 1287.05109, MR 3126677, 10.1016/j.dam.2013.06.025 |
| Reference:
|
[18] Tokunaga, S.: On domination number of triangulated discs.J. Inf. Process. 28 (2020), 846-848. 10.2197/ipsjjip.28.846 |
| . |
