Cops and robber on subclasses of P5-free graphs
| dc.contributor.author | Uttam K, Gupta | |
| dc.contributor.author | Suchismita, Mishra | |
| dc.contributor.author | Dinabandhu, Pradhan | |
| dc.date.accessioned | 2023-03-22T12:52:31Z | |
| dc.date.available | 2023-03-22T12:52:31Z | |
| dc.date.issued | 2023-06 | |
| dc.description | IDEXACIÓN:SCOPUS | es |
| dc.description.abstract | The game of cops and robber is a turn-based vertex pursuit game played on a connected graph between a team of cops and a single robber. The cops and the robber move alternately along the edges of the graph. We say that the team of cops wins the game if a cop and the robber are at the same vertex of the graph. The minimum number of cops required to win in a connected graph is called the cop number of the graph. Sivaraman (2019) [16] conjectured that for every t≥5, the cop number of a connected Pt-free graph is at most t−3, where Pt denotes a path on t vertices. Turcotte (2022) [18] showed that the cop number of any 2K2-free graph is at most 2, which was earlier conjectured by Sivaraman and Testa. Note that if a connected graph is 2K2-free, then it is also P5-free. Liu showed that the cop number of a connected (Pt, H)-free graph is at most t−3, where H is a cycle of length at most t or a claw. So the conjecture of Sivaraman is true for (P5, H)-free graphs, where H is a cycle of length at most 5 or a claw. In this paper, we show that the cop number of a connected (P5,H)-free graph is at most 2, where H∈{diamond, paw, K4, 2K1∪K2, K3∪K1}. © 2023 Elsevier B.V. | es |
| dc.identifier.citation | Discrete MathematicsOpen AccessVolume 346, Issue 6June 2023 Article number 113353 | es |
| dc.identifier.issn | 0012365X | |
| dc.identifier.uri | https://repositorio.unab.cl/xmlui/handle/ria/47747 | |
| dc.language.iso | en | es |
| dc.subject | Cop number; Cops and robber; Forbidden induced subgraphs; P5-free graphs | es |
| dc.title | Cops and robber on subclasses of P5-free graphs | es |
| dc.type | Artículo | es |
Archivos
Bloque original
1 - 1 de 1
Cargando...
- Nombre:
- Uttam K-Cops and robber on subclasses of P5-free graphs.pdf
- Tamaño:
- 529.94 KB
- Formato:
- Adobe Portable Document Format
- Descripción:
- TEXTO COMPLETO EN INGLÉS
Bloque de licencias
1 - 1 de 1
No hay miniatura disponible
- Nombre:
- license.txt
- Tamaño:
- 1.71 KB
- Formato:
- Item-specific license agreed upon to submission
- Descripción: