The 2-domination number of cylindrical graphs
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866912045795901440 |
|---|---|
| author | Martínez, José Antonio Castaño-Fernández, Ana Belén Puertas, María Luz |
| author_facet | Martínez, José Antonio Castaño-Fernández, Ana Belén Puertas, María Luz |
| contents | A vertex subset S of a graph G is said to 2-dominate the graph if each vertex not in S has at least two neighbors in it. As usual, the associated parameter is the minimum cardinal of a 2-dominating set, which is called the 2-domination number of the graph G. We present both lower and upper bounds of the 2-domination number of cylinders, which are the Cartesian products of a path and a cycle. These bounds allow us to compute the exact value of the 2-domination number of cylinders where the path is arbitrary, and the order of the cycle is n $\equiv$ 0(mod 3) and as large as desired. In the case of the lower bound, we adapt the technique of the wasted domination to this parameter and we use the so-called tropical matrix product to obtain the desired bound. Moreover, we provide a regular patterned construction of a minimum 2-dominating set in the cylinders having the mentioned cycle order. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2409_16703 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | The 2-domination number of cylindrical graphs Martínez, José Antonio Castaño-Fernández, Ana Belén Puertas, María Luz Combinatorics Discrete Mathematics 05C69, 05C85, 15A80 A vertex subset S of a graph G is said to 2-dominate the graph if each vertex not in S has at least two neighbors in it. As usual, the associated parameter is the minimum cardinal of a 2-dominating set, which is called the 2-domination number of the graph G. We present both lower and upper bounds of the 2-domination number of cylinders, which are the Cartesian products of a path and a cycle. These bounds allow us to compute the exact value of the 2-domination number of cylinders where the path is arbitrary, and the order of the cycle is n $\equiv$ 0(mod 3) and as large as desired. In the case of the lower bound, we adapt the technique of the wasted domination to this parameter and we use the so-called tropical matrix product to obtain the desired bound. Moreover, we provide a regular patterned construction of a minimum 2-dominating set in the cylinders having the mentioned cycle order. |
| title | The 2-domination number of cylindrical graphs |
| topic | Combinatorics Discrete Mathematics 05C69, 05C85, 15A80 |
| url | https://arxiv.org/abs/2409.16703 |