The damage number of the Cartesian product of graphs
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866917872021798912 |
|---|---|
| author | Huggan, Melissa A. Messinger, Margaret-Ellen Porter, Amanda |
| author_facet | Huggan, Melissa A. Messinger, Margaret-Ellen Porter, Amanda |
| contents | We consider a variation of Cops and Robber, introduced in [D. Cox and A. Sanaei, The damage number of a graph, [Aust. J. of Comb. 75(1) (2019) 1-16] where vertices visited by a robber are considered damaged and a single cop aims to minimize the number of distinct vertices damaged by a robber. Motivated by the interesting relationships that often emerge between input graphs and their Cartesian product, we study the damage number of the Cartesian product of graphs. We provide a general upper bound and consider the damage number of the product of two trees or cycles. We also consider graphs with small damage number. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2308_09645 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | The damage number of the Cartesian product of graphs Huggan, Melissa A. Messinger, Margaret-Ellen Porter, Amanda Combinatorics Discrete Mathematics 05C57, 68R10 We consider a variation of Cops and Robber, introduced in [D. Cox and A. Sanaei, The damage number of a graph, [Aust. J. of Comb. 75(1) (2019) 1-16] where vertices visited by a robber are considered damaged and a single cop aims to minimize the number of distinct vertices damaged by a robber. Motivated by the interesting relationships that often emerge between input graphs and their Cartesian product, we study the damage number of the Cartesian product of graphs. We provide a general upper bound and consider the damage number of the product of two trees or cycles. We also consider graphs with small damage number. |
| title | The damage number of the Cartesian product of graphs |
| topic | Combinatorics Discrete Mathematics 05C57, 68R10 |
| url | https://arxiv.org/abs/2308.09645 |