On the 2-domination Number of Cylinders with Small Cycles.

• Autorzy: Garzón Ester M. , Martínez José A. , Moreno Juan J.

Identyfikatory

DOI

10.3233/FI-222107

• Języki publikacji: EN

Abstrakty

EN

Domination-type parameters are difficult to manage in Cartesian product graphs and there is usually no general relationship between the parameter in both factors and in the product graph. This is the situation of the domination number, the Roman domination number or the 2-domination number, among others. Contrary to what happens with the domination number and the Roman domination number, the 2-domination number remains unknown in cylinders, that is, the Cartesian product of a cycle and a path and in this paper, we will compute this parameter in the cylinders with small cycles. We will develop two algorithms involving the (min, +) matrix product that will allow us to compute the desired values of γ2(Cn□Pm), with 3 ≤ n ≤ 15 and m ≤ 2. We will also pose a conjecture about the general formula for the 2-domination number in this graph class.

Słowa kluczowe

EN

2-domination; Cartesian product; (min, +) matrix product

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2022
• Tom: Vol. 185, nr 2
• Strony: 185--199
• Opis fizyczny: Bibliogr. 18 poz., tab.

Twórcy

autor

Garzón Ester M.

• Department of Computer Sciences and Agrifood Campus of International Excellence (ceiA3), Universidad de Almería, Carretera Sacramento s/n, 04120 Almería, Spain.

autor

Martínez José A.

• Department of Computer Sciences and Agrifood Campus of International Excellence (ceiA3), Universidad de Almería, Carretera Sacramento s/n, 04120 Almería, Spain.

autor

Moreno Juan J.

• Department of Computer Sciences and Agrifood Campus of International Excellence (ceiA3), Universidad de Almería, Carretera Sacramento s/n, 04120 Almería, Spain.

Bibliografia

• [1] Haynes T, Hedetniemi S, Slater P. Fundamentals of Domination in Graphs. Chapman and Hall/CRC Pure and Applied Mathematics Series. Marcel Dekker, Inc. New York, 1998. ISBN 9780824700331.
• [2] Butjás C. Domination number of graphs with minimum degree five. Discuss. Math. Graph Theory, 2021. 41(3):763777. doi:10.7151/dmgt.2339. URL https://www.dmgt.uz.zgora.pl/publish/bbl_view_pdf.php?ID=48418.
• [3] Abdollahzadeh Ahangar H, Amjadi J, Chellali M, Nazari-Moghaddam S, Sheikholeslami S. Total 2-rainbow domination numbers in tress. Discuss. Math. Graph Theory, 2021. 41(2):345364. doi:10.7151/dmgt.2191. URL https://www.dmgt.uz.zgora.pl/publish/bbl_view_pdf.php?ID=45565.
• [4] Fink J, Jacobson M. N-Domination in Graphs, p. 283300. Graph Theory with Applications to Algorithmsnand Computer Science. John Wiley & Sons, Inc., USA. ISBN 0471816353, 1985.
• [5] Bonomo F, Brešar B, Grippo L, Milanič M, Safe M. Domination parameters with number 2: Interrelations and algorithmic consequences. Discrete Applied Mathematics, 2018. 235:23-50. doi:10.1016/j.dam.2017.08.017. URL https://doi.org/10.1016/j.dam.2017.08.017.
• [6] Imrich W, Klavžar S. Product graphs, structure and recognition. Wiley-Interscience series in discrete mathematics and optimization. Wiley, 2000. ISBN 9780471370390.
• [7] Vizing VG. Some unsolved problems in graph theory. Uspekhi Mat. Nauk, 1968. 23(6(144)):117-134. URL http://mi.mathnet.ru/eng/umn/v23/i6/p117.
• [8] Brešar B, Dorbec P, Goddard W, Hartnell BL, Henning MA, Klavžar S, Rall DF. Vizing’s conjecture: a survey and recent results. Journal of Graph Theory, 2012. 69(1):46-76. doi:10.1002/jgt.20565. URL http://dx.doi.org/10.1002/jgt.20565.
• [9] Brešar B, Hartnell B, Henning M, Kuenzel K, Rall D. A new framework to approach Vizings conjecture. Discuss. Math. Graph Theory, 2021. 41(3):749762. doi:10.7151/dmgt.2293. URL https://www.dmgt.uz.zgora.pl/publish/bbl_view_pdf.php?ID=48419.
• [10] Rao M, Talon A. The 2-domination and Roman domination numbers of grid graphs. Discrete Math. Theor. Comput. Sci., 2019. 21(1):1-14. doi:10.23638/DMTCS-21-1-9. URL https://doi.org/10.23638/DMTCS-21-1-9.
• [11] Shaheen R. Bounds for the 2-domination number of toroidal grid graphs. International Journal of Computer Mathematics, 2009. 86(4):584-588. doi:10.1080/00207160701690284. URL https://doi.org/10.1080/00207160701690284.
• [12] Pin JE. Tropical semirings, , chapter 2, pp. 50-69. Idempotency (J. Gunawardena, Ed.) Publications of the Newton Institute. Cambridge University Press, 1998. doi:10.1017/CBO9780511662508.004. URL https://doi.org/10.1017/CBO9780511662508.004.
• [13] Klavžar S, Žerovnik J. Algebraic approach to fasciagraphs and rotagraphs. Discret. Appl. Math., 1996. 68(1):93-100. doi:10.1016/0166-218X(95)00058-Y. URL https://www.sciencedirect.com/science/article/pii/0166218X9500058Y.
• [14] Spalding A. Min-Plus Algebra and Graph Domination. Ph.D. thesis, Dept. of Appl. Math., Univ. of Colorado, Denver, CL, USA, 1998. URL https://math.ucdenver.edu/graduate/thesis/spalding.pdf.
• [15] Gonçalves D, Pinlou A, Rao M, Thomassé S. The Domination Number of Grids. SIAM J. Discret. Math., 2011. 25(3):1443-1453. doi:10.1137/11082574. URL https://doi.org/10.1137/11082574
• [16] Pavlič P, Žerovnik J. Roman Domination Number of the Cartesian Products of Paths and Cycles. Electron. J. Comb., 2012. 19(3):P19. URL http://www.combinatorics.org/ojs/index.php/eljc/article/view/v19i3p19.
• [17] Pavlič P, Žerovnik J. A note on the domination number of the Cartesian products of paths and cycles. Kragujevac J. Math., 2013. 37(2):275-285. URL http://elib.mi.sanu.ac.rs/files/journals/kjm/41/kjom3702-07.pdf.
• [18] Davis T. CSPARSE. A Concise Sparse Matrix Package in C. https://github.com/ibayer/CSparse/2014.

Uwagi

Opracowanie rekordu ze środków MEiN, umowa nr SONP/SP/546092/2022 w ramach programu "Społeczna odpowiedzialność nauki" - moduł: Popularyzacja nauki i promocja sportu (2022-2023). (PL)