Détail du document
Identifiant
oai:arXiv.org:2408.02225
Sujet
Mathematics - Combinatorics Computer Science - Discrete Mathem... 05C57, 05C75Auteur
Clow, Alexander Huggan, Melissa A. Messinger, M. E.Catégorie
Computer Science
Année
2024
Date de référencement
07/08/2024
Mots clés
attacking graphs cops $\attcop $g$ robbersRésumé
This paper considers the Cops and Attacking Robbers game, a variant of Cops and Robbers, where the robber is empowered to attack a cop in the same way a cop can capture the robber.
In a graph $G$, the number of cops required to capture a robber in the Cops and Attacking Robbers game is denoted by $\attCop(G)$.
We characterise the triangle-free graphs $G$ with $\attCop(G) \leq 2$ via a natural generalisation of the cop-win characterisation by Nowakowski and Winkler \cite{nowakowski1983vertex}.
We also prove that all bipartite planar graphs $G$ have $\attCop(G) \leq 4$ and show this is tight by constructing a bipartite planar graph $G$ with $\attCop(G) = 4$.
Finally we construct $17$ non-isomorphic graphs $H$ of order $58$ with $\attCop(H) = 6$ and $\cop(H)=3$.
This provides the first example of a graph $H$ with $\attCop(H) - \cop(H) \geq 3$ extending work by Bonato, Finbow, Gordinowicz, Haidar, Kinnersley, Mitsche, Pra\l{}at, and Stacho \cite{bonato2014robber}.
We conclude with a list of conjectures and open problems.
;Comment: 25 pages, 5 figures
Clow, Alexander,Huggan, Melissa A.,Messinger, M. E., 2024, Cops and Attacking Robbers with Cycle Constraints
MELAS: Phenotype Classification into Classic-versus-Atypical Presentations
presentations mitochondrial strokelike patients variability phenotype clinical melas
