تقرير
The damage number of the Cartesian product of graphs
العنوان: | The damage number of the Cartesian product of graphs |
---|---|
المؤلفون: | Huggan, Melissa A., Messinger, Margaret-Ellen, Porter, Amanda |
سنة النشر: | 2023 |
المجموعة: | Computer Science Mathematics |
مصطلحات موضوعية: | Mathematics - Combinatorics, Computer Science - 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. Comment: 21 pages, 3 figures |
نوع الوثيقة: | Working Paper |
URL الوصول: | http://arxiv.org/abs/2308.09645 |
رقم الأكسشن: | edsarx.2308.09645 |
قاعدة البيانات: | arXiv |
الوصف غير متاح. |