A bound for the cops and robber problem in terms of 2-component order connectivity
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866929613293223936 |
|---|---|
| author | Jain, Suryaansh Kalyanasundaram, Subrahmanyam Tammana, Kartheek Sriram |
| author_facet | Jain, Suryaansh Kalyanasundaram, Subrahmanyam Tammana, Kartheek Sriram |
| contents | In the cops and robber game, there are multiple cops and a single robber taking turns moving along the edges of a graph. The goal of the cops is to capture the robber (move to the same vertex as the robber) and the goal of the robber is to avoid capture. The cop number of a given graph is the smallest number of cops required to ensure the capture of the robber. The k-component order connectivity of a graph G = (V, E) is the size of a smallest set U, such that all the connected components of the induced graph on V \ U are of size at most k. In this brief note, we provide a bound on the cop number of graphs in terms of their 2-component order connectivity. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2412_02511 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | A bound for the cops and robber problem in terms of 2-component order connectivity Jain, Suryaansh Kalyanasundaram, Subrahmanyam Tammana, Kartheek Sriram Combinatorics Discrete Mathematics In the cops and robber game, there are multiple cops and a single robber taking turns moving along the edges of a graph. The goal of the cops is to capture the robber (move to the same vertex as the robber) and the goal of the robber is to avoid capture. The cop number of a given graph is the smallest number of cops required to ensure the capture of the robber. The k-component order connectivity of a graph G = (V, E) is the size of a smallest set U, such that all the connected components of the induced graph on V \ U are of size at most k. In this brief note, we provide a bound on the cop number of graphs in terms of their 2-component order connectivity. |
| title | A bound for the cops and robber problem in terms of 2-component order connectivity |
| topic | Combinatorics Discrete Mathematics |
| url | https://arxiv.org/abs/2412.02511 |