{
  "$type": "site.standard.document",
  "bskyPostRef": {
    "cid": "bafyreifrq5obwzt3sx46xhehtroerwaugw4pmokst4bj3jnmxsvlhygq7q",
    "uri": "at://did:plc:4rgrdigiftglskeax4wvmsev/app.bsky.feed.post/3mk2qkdtfwgr2"
  },
  "coverImage": {
    "$type": "blob",
    "ref": {
      "$link": "bafkreiflo6xt7is6b2iafwghkjahlgggocme5jwjsbeuqqwcywuvjhmszm"
    },
    "mimeType": "image/png",
    "size": 24783
  },
  "path": "/abs/2604.18949v1",
  "publishedAt": "2026-04-22T00:00:00.000Z",
  "site": "https://arxiv.org",
  "tags": [
    "Dohoon Kim",
    "Eungyu Woo",
    "Donghoon Shin"
  ],
  "textContent": "**Authors:** Dohoon Kim, Eungyu Woo, Donghoon Shin\n\nThis paper investigates a special variant of a pursuit-evasion game called lions and contamination. In a graph where all vertices are initially contaminated, a set of lions traverses the graph, clearing the contamination from every vertex they visit. However, the contamination simultaneously spreads to any adjacent vertex not occupied by a lion. We analyze the relationships among the lion number $\\mathcal{L}(G)$, monotone lion number $\\mathcal{L}^m(G)$, and the graph's pathwidth $\\operatorname{pw}(G)$. Our main results are as follows: (a) We prove a monotonicity property: for any graph $G$ and its isometric subgraph $H$, $\\mathcal{L}(H)\\le \\mathcal{L}(G)$. (b) For trees $T$, we show that the lion number is tightly characterized by pathwidth, satisfying $\\operatorname{pw}(T)\\le \\mathcal{L}(T)\\le \\operatorname{pw}(T)+1$. (c) We provide a counterexample showing that the monotonicity property fails for arbitrary subgraphs. (d) We show that, in contrast to the tree case, pathwidth does not yield a general lower bound on $\\mathcal{L}(G)$ for arbitrary graphs. (e) For any connected graph $G$, we prove the general upper bound $\\mathcal{L}(G)\\le \\operatorname{pw}(G)+1$. (f) For the monotone variant, we establish the general lower bound $\\operatorname{pw}(G)\\le \\mathcal{L}^m(G)$. (g) Conversely, we show that $\\mathcal{L}^m(G)\\le 2\\operatorname{pw}(G)+2$ holds for all connected graphs, which is best possible up to a small additive constant.",
  "title": "Lions and Contamination: Trees and General Graphs"
}