Pushing Cops and Robber on Graphs of Maximum Degree 4
Fuente:
arXiv
Salvato in:
| Autore principale: | |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866917169135091712 |
|---|---|
| author | Gahlawat, Harmender |
| author_facet | Gahlawat, Harmender |
| contents | \textsc{Cops and Robber} is a game played on graphs where a set of \textit{cops} aim to \textit{capture} the position of a single \textit{robber}. The main parameter of interest in this game is the \textit{cop number}, which is the minimum number of cops that are sufficient to guarantee the capture of the robber.
In a directed graph $\overrightarrow{G}$, the \textit{push} operation on a vertex $v$ reverses the orientation of all arcs incident on $v$. We consider a variation of classical \textsc{Cops and Robber} on oriented graphs, where in its turn, each cop can either move to an out-neighbor of its current vertex or push some vertex of the graph, whereas, the robber can move to an adjacent vertex in its turn. [Das et al., CALDAM, 2023] introduced this variant and established that if $\overrightarrow{G}$ is an orientation of a subcubic graph, then one cop with push ability has a winning strategy. We extend these results to establish that if $\overrightarrow{G}$ is an orientation of a $3$-degenerate graph, or of a graph with maximum degree $4$, then one cop with push ability has a winning strategy. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2505_21450 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Pushing Cops and Robber on Graphs of Maximum Degree 4 Gahlawat, Harmender Combinatorics Discrete Mathematics \textsc{Cops and Robber} is a game played on graphs where a set of \textit{cops} aim to \textit{capture} the position of a single \textit{robber}. The main parameter of interest in this game is the \textit{cop number}, which is the minimum number of cops that are sufficient to guarantee the capture of the robber. In a directed graph $\overrightarrow{G}$, the \textit{push} operation on a vertex $v$ reverses the orientation of all arcs incident on $v$. We consider a variation of classical \textsc{Cops and Robber} on oriented graphs, where in its turn, each cop can either move to an out-neighbor of its current vertex or push some vertex of the graph, whereas, the robber can move to an adjacent vertex in its turn. [Das et al., CALDAM, 2023] introduced this variant and established that if $\overrightarrow{G}$ is an orientation of a subcubic graph, then one cop with push ability has a winning strategy. We extend these results to establish that if $\overrightarrow{G}$ is an orientation of a $3$-degenerate graph, or of a graph with maximum degree $4$, then one cop with push ability has a winning strategy. |
| title | Pushing Cops and Robber on Graphs of Maximum Degree 4 |
| topic | Combinatorics Discrete Mathematics |
| url | https://arxiv.org/abs/2505.21450 |