Cops and robber on subclasses of P5-free graphs
Cargando...
Archivos
Fecha
2023-06
Profesor/a Guía
Facultad/escuela
Idioma
en
Título de la revista
ISSN de la revista
Título del volumen
Editor
Nombre de Curso
Licencia CC
Licencia CC
Resumen
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.
Notas
IDEXACIÓN:SCOPUS
Palabras clave
Cop number; Cops and robber; Forbidden induced subgraphs; P5-free graphs
Citación
Discrete MathematicsOpen AccessVolume 346, Issue 6June 2023 Article number 113353