تقرير
The Game of Cops and Robber on (Claw, Even-hole)-free Graphs
| العنوان: | The Game of Cops and Robber on (Claw, Even-hole)-free Graphs |
|---|---|
| المؤلفون: | Javadi, Ramin, Momeni, Ali |
| سنة النشر: | 2021 |
| المجموعة: | Computer Science Mathematics |
| مصطلحات موضوعية: | Mathematics - Combinatorics, Computer Science - Discrete Mathematics |
| الوصف: | In this paper, we study the game of cops and robber on the class of graphs with no even hole (induced cycle of even length) and claw (a star with three leaves). The cop number of a graph $G$ is defined as the minimum number of cops needed to capture the robber. Here, we prove that the cop number of all claw-free even-hole-free graphs is at most two and, in addition, the capture time is at most $2n$ rounds, where $n$ is the number of vertices of the graph. Moreover, our results can be viewed as a first step towards studying the structure of claw-free even-hole-free graphs. |
| نوع الوثيقة: | Working Paper |
| URL الوصول: | http://arxiv.org/abs/2112.07503 |
| رقم الأكسشن: | edsarx.2112.07503 |
| قاعدة البيانات: | arXiv |
| الوصف غير متاح. |