Distance-k Domination Number in Triangular Matchstick Graphs and Triangulated Rectangular Grids
Resumo
A distance-k dominating set of a graph is a set of vertices such that every vertex lies within distance k of some vertex in the set; its minimum size is the distance-k domination number γk. We study γk for triangular matchstick graphs and triangulated rectangular grids. For triangulated rectangular grids, we give upper bounds for γ and γ2. For triangular matchstick graphs Td, we correct two upper-bound statements of Harris et al. [Harris et al. 2020], improve the bound for k = 1, derive an upper bound for k = 2 and relate γk to the radius of Td.
Referências
Blessing, D., Johnson, K., Mauretour, C., and Insko, E. (2015). On (t, r) broadcast domination numbers of grids. Discrete Applied Mathematics, 187:19–40.
Bondy, J. A. and Murty, U. S. R. (2008). Graph Theory, volume 244 of Graduate Texts in Mathematics. Springer, New York, NY, USA.
Bose, P., Gledel, V., Pennarun, C., and Verdonschot, S. (2020). Power domination on triangular grids with triangular and hexagonal shape. Journal of Combinatorial Optimization, 40(2):482–500.
Chang, T. Y. and Clark, W. E. (1993). The domination numbers of the 5 × n and 6 × n grid graphs. Journal of Graph Theory, 17(1):81–107.
Christiansen, A. B. G., Rotenberg, E., and Rutschmann, D. (2024). Triangulations admit dominating sets of size 2n/7. In Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1194–1240. SIAM.
Diestel, R. (2017). Graph Theory, volume 173 of Graduate Texts in Mathematics. Springer, Berlin, Heidelberg, 5th edition.
Fata, E., Smith, S. L., and Sundaram, S. (2013). Distributed dominating sets on grids. In Proceedings of the 2013 American Control Conference (ACC), pages 211–216. IEEE.
Gonçalves, D., Pinlou, A., Rao, M., and Thomassé, S. (2011). The domination number of grids. SIAM Journal on Discrete Mathematics, 25(3):1443–1453.
Harris, P. E., Luque, D. K., Reyes Flores, C., and Sepulveda, N. (2020). Efficient (t, r) broadcast dominating sets of the triangular lattice. Discrete Applied Mathematics, 277:180–192.
Haynes, T. W., Hedetniemi, S. T., and Henning, M. A., editors (2020). Topics in Domination in Graphs, volume 64 of Developments in Mathematics. Springer, Cham.
Hongo, P. F. and Campos, C. N. (2013). Dominating sets in planar graphs. Technical Report IC-13-22, Institute of Computing, University of Campinas.
Jacobson, M. S. and Kinch, L. F. (1983). On the domination number of products of graphs: I. Ars Combinatoria, 18:33–44.
King, A. D. and Pelsmajer, M. J. (2010). Dominating sets in plane triangulations. Discrete Mathematics, 310(17-18):2221–2230.
Matheson, L. R. and Tarjan, R. E. (1996). Dominating sets in planar graphs. European Journal of Combinatorics, 17(6):565–568.
Plummer, M. D. and Zha, X. (2016). Dominating plane triangulations. Discrete Mathematics, 339(11):2723–2731.
Slater, P. J. (1976). R-domination in graphs. Journal of the ACM, 23(3):446–450.
Špacapan, S. (2020). The domination number of plane triangulations. Journal of Combinatorial Theory, Series B, 143:42–64.
Bondy, J. A. and Murty, U. S. R. (2008). Graph Theory, volume 244 of Graduate Texts in Mathematics. Springer, New York, NY, USA.
Bose, P., Gledel, V., Pennarun, C., and Verdonschot, S. (2020). Power domination on triangular grids with triangular and hexagonal shape. Journal of Combinatorial Optimization, 40(2):482–500.
Chang, T. Y. and Clark, W. E. (1993). The domination numbers of the 5 × n and 6 × n grid graphs. Journal of Graph Theory, 17(1):81–107.
Christiansen, A. B. G., Rotenberg, E., and Rutschmann, D. (2024). Triangulations admit dominating sets of size 2n/7. In Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1194–1240. SIAM.
Diestel, R. (2017). Graph Theory, volume 173 of Graduate Texts in Mathematics. Springer, Berlin, Heidelberg, 5th edition.
Fata, E., Smith, S. L., and Sundaram, S. (2013). Distributed dominating sets on grids. In Proceedings of the 2013 American Control Conference (ACC), pages 211–216. IEEE.
Gonçalves, D., Pinlou, A., Rao, M., and Thomassé, S. (2011). The domination number of grids. SIAM Journal on Discrete Mathematics, 25(3):1443–1453.
Harris, P. E., Luque, D. K., Reyes Flores, C., and Sepulveda, N. (2020). Efficient (t, r) broadcast dominating sets of the triangular lattice. Discrete Applied Mathematics, 277:180–192.
Haynes, T. W., Hedetniemi, S. T., and Henning, M. A., editors (2020). Topics in Domination in Graphs, volume 64 of Developments in Mathematics. Springer, Cham.
Hongo, P. F. and Campos, C. N. (2013). Dominating sets in planar graphs. Technical Report IC-13-22, Institute of Computing, University of Campinas.
Jacobson, M. S. and Kinch, L. F. (1983). On the domination number of products of graphs: I. Ars Combinatoria, 18:33–44.
King, A. D. and Pelsmajer, M. J. (2010). Dominating sets in plane triangulations. Discrete Mathematics, 310(17-18):2221–2230.
Matheson, L. R. and Tarjan, R. E. (1996). Dominating sets in planar graphs. European Journal of Combinatorics, 17(6):565–568.
Plummer, M. D. and Zha, X. (2016). Dominating plane triangulations. Discrete Mathematics, 339(11):2723–2731.
Slater, P. J. (1976). R-domination in graphs. Journal of the ACM, 23(3):446–450.
Špacapan, S. (2020). The domination number of plane triangulations. Journal of Combinatorial Theory, Series B, 143:42–64.
Publicado
19/07/2026
Como Citar
GUTIERREZ, Juan; NEIRA, Jorge.
Distance-k Domination Number in Triangular Matchstick Graphs and Triangulated Rectangular Grids. In: ENCONTRO DE TEORIA DA COMPUTAÇÃO (ETC), 11. , 2026, Gramado/RS.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2026
.
p. 95-123.
ISSN 2595-6116.
DOI: https://doi.org/10.5753/etc.2026.21131.
