4 K 1 4K_{1} -free graph with the cop number 3 3
2025
Read 4 K 1 4K_{1} -free graph with the cop number 3 3 (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2505-15416.txt.
Introduction
Arnab Char, Paras Vinubhai Maniya, and Dinabandhu Pradhan study a pursuit game on graphs in a 2025 paper. In the game of cops and robber, cop pieces chase a robber piece across the corners of a graph. The cop number is the fewest cops that can force a capture. A past guess claimed that graphs avoiding long cycles need at most two cops.
The authors disprove that guess with one sharp example. The mirror image of a known graph, the Shrikhande graph, avoids the banned patterns yet needs three cops. That answer also settles a related question about graphs that avoid sets of isolated corners. The team then proves a bound for a wider family and adds degree thresholds that speed up finding cop numbers.
Catalog record
| YEAR | 2025 |
|---|---|
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 62 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2505-15416
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
4 K 1 4K_{1} -free graph with the cop number 3 3 Thanks: Corresponding author. Affiliation: National Institute of InformaticsTokyo, Japan Email: [email protected] Thanks: Supported in part by Core Research Grant, ANRF, India (CRG/2023/003749) Affiliation: Arnab Char, Paras Vinubhai Maniya, and Dinabandhu Pradhan Affiliation: Department of Mathematics & ComputingIndian Institute of Technology (ISM)Dhanbad, India Email: [email protected]: [email protected] Abstract The game of cops and robber is a two-player turn-based game played on a graph where the cops try to capture the robber. The cop number of a graph G G , denoted by c ( G ) c(G) is the minimum number of cops required to capture the robber. For a given class of graphs ℱ {\cal F} , let c ( ℱ ) := sup { c ( F ) | F ∈ ℱ } c({\cal F}):=\sup\{c(F)|F\in{\cal F}\} , and let Forb ( ℱ ) ({\cal F}) denote the class of ℱ {\cal F} -free graphs. We show that the complement of the Shrikhande graph is ( 4 K 1 , C ℓ CLOSE (4K_{1},C_{\ell} )-free for any ℓ ≥ 6 \ell\geq 6 and has the cop number 3 3 . This provides a counterexample for the conjecture proposed by Sivaraman [ 14 ] which states that if G G is C ℓ C_{\ell} -free for all ℓ ≥ 6 \ell\geq 6 , then c ( G ) ≤ 2 c(G)\leq 2 . This also gives a negative answer to the question posed by Turcotte [ 16 ] to check whether c ( CLOSE c( Forb OPEN ( p K 1 ) ) = p − 2 (pK_{1}))=p-2 for p ≥ 4 p\geq 4 . Turcotte also posed the question to check whether c ( CLOSE c( Forb OPEN ( p K 1 + K 2 ) ) ≤ p + 1 (pK_{1}+K_{2}))\leq p+1 for p ≥ 3 p\geq 3 . We prove that this result indeed holds. We also generalize this result for Forb ( p K 1 + q K 2 ) (pK_{1}+qK_{2}) . Motivated by the results of Baird et al. [ 2 ] and Turcotte and Yvon [ 15 ] , we define the upper threshold degree and lower threshold degree for a particular class of graphs and show some computational advantage to find the cop number using these. Keywords: Cops and robber; cop number; the Shrikhande graph; 4K_{1} -free graphs; pK_{1}+qK_{2} -free graphs. AMS subject classification: 05C57 1 Introduction We consider finite, simple, undirected, and connected graphs in this paper. For a given graph G , let V(G) and E(G) denote the vertex set and the edge set of G , respectively. The complement of a graph G , denoted as \overline{G} , is the graph with the vertex set V(\overline{G})=V(G) and the edge set E(\overline{G})=\{uv\mid uv\notin E(G)\} . Let X\subseteq V(G) . The subgraph of G induced by the vertex set X is denoted by G[X] , and the subgraph of G induced by the vertex set V(G)\setminus X is denoted by G\setminus X . The set X is called a clique (independent set) if every pair of vertices of X are adjacent (nonadjacent) in G . For any two nonempty sets, say X,Y\subseteq V(G) , X is complete (anticomplete) to Y if every vertex in X is adjacent (nonadjacent) to every vertex in Y . The open neighborhood of a vertex x in G , denoted by N_{G}(x) , is the set of all adjacent vertices to x . The closed neighborhood of x in G , denoted by N_{G}[x] , is the set N_{G}(x)\cup\{x\} . The degree of a vertex x in G is defined as |N_{G}(x)| and is denoted by d_{G}(x) . We denote \delta(G) as the minimum degree of G , where \delta(G)=\min\{d_{G}(x)\mid x\in V(G)\} . We denote \Delta(G) as the maximum degree of G , where \Delta(G)=\max\{d_{G}(x)\mid x\in V(G)\} . We drop the subscript G when there is no ambiguity. Let C_{\ell} , K_{\ell} , and P_{\ell} denote the induced cycle, the induced complete graph, and the induced path on \ell vertices, where \ell\geq 1 . To avoid ambiguity, we will write K_{i} instead of P_{i} for i\in\{1,2\} . If G_{1} and G_{2} are two vertex disjoint graphs, then the disjoint union of G_{1} and G_{2} , denoted by G_{1}+G_{2} , is the graph with vertex set V(G_{1})\cup V(G_{2}) and edge set E(G_{1})\cup E(G_{2}) . For a given graph G and \ell\in\mathbb{N} , we denote \ell G as the disjoint union of \ell copies of G . So \ell K_{1} is the graph obtained from the disjoint union of \ell copies of K_{1} . For a given graph G , we say G is {\cal F} -free if for any F\in{\cal F} , F is not an induced subgraph of G . For a given class of graphs {\cal G} , we say {\cal G} is {\cal F} -free if for all G\in{\cal G} , G is {\cal F} -free. If {\cal F}=\{F\} , we simply say G is F -free, and {\cal G} is F -free. We denote the class of {\cal F} -free graphs as Forb ({\cal F}) . The game of cops and robber is a well studied problem in graph theory as can be seen in literature (see [ 1 , 5 , 11 , 15 ] ). Quilliot [ 12 ] introduced the game of cops and robber in 1978 and later, Nowakowski and Winkler [ 9 ] studied the above game independently. The game is a turn-based game and is played on a connected graph by two players. For a given graph G , player one controls the movement of a set of cops, say D=\{D_{1},D_{2},\ldots,D_{p}\} , and player two controls the movement of a robber, say R , by putting them on vertices of G . A round of the game consists of two consecutive turns started with the turn of the player one and ended with the turn of the player two. The game is started by the player one by putting the cops in the vertices of G and in the next turn, the player two puts the robber in a vertex of G . Clearly, this is round 1 of the game. After that, the game is played on by alternative turns of the player one and the player two. For r\in\mathbb{N} and i\in\{1,2,\ldots,p\} , let p_{r}^{G}(D_{i}) be the vertex, where the cop D_{i} is placed at the round r of the game in G . For r\in\mathbb{N} , let p_{r}^{G}(R) be the vertex, where the robber R is placed at the round r in G . We drop the superscript G when there is no ambiguity. For each r\geq 2 , a move played by the player one in the round r is legal if the player one puts L in p_{r-1}(L) or in some adjacent vertex of p_{r-1}(L) , where L\in D . For each r\geq 2 , a move played by the player two in the round r is legal if the player two puts R in p_{r-1}(R) or in some adjacent vertex of p_{r-1}(R) . A cop captures the robber if they are