Lions and Contamination: Trees and General Graphs
Pith reviewed 2026-05-10 03:01 UTC · model grok-4.3
The pith
Lion numbers on trees equal pathwidth or pathwidth plus one, and monotone lion numbers on graphs lie between pathwidth and twice pathwidth plus two.
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
Core claim
The paper proves that for any tree T the lion number L(T) is bounded below by the pathwidth pw(T) and above by pw(T)+1. It further shows that every connected graph G satisfies L(G) ≤ pw(G)+1, while the monotone lion number obeys pw(G) ≤ L^m(G) ≤ 2 pw(G)+2. The upper bound on L^m is asymptotically tight up to a small additive constant, and monotonicity of L holds for isometric subgraphs but fails for arbitrary subgraphs.
What carries the argument
The lion number L(G) (and its monotone version L^m(G)), defined as the minimum number of lions whose traversal clears all contamination despite simultaneous spread to unoccupied neighbors.
Load-bearing premise
The contamination spreads to every unoccupied adjacent vertex at each discrete step and lions clear precisely the vertices they occupy.
What would settle it
A concrete tree T whose lion number differs from pw(T) by more than one, or a connected graph G whose monotone lion number exceeds 2 pw(G)+2.
read the original abstract
This 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.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. This paper studies the lions and contamination pursuit-evasion game on graphs, where lions clear contamination that spreads to adjacent unoccupied vertices. It defines the lion number L(G) and monotone lion number L^m(G), and establishes their relationships to pathwidth pw(G). The main results include: monotonicity L(H) ≤ L(G) for isometric subgraphs H; the tight bounds pw(T) ≤ L(T) ≤ pw(T)+1 for any tree T; a counterexample showing monotonicity fails for non-isometric subgraphs; that pw does not lower-bound L on general graphs; the upper bound L(G) ≤ pw(G)+1 for connected graphs; the lower bound pw(G) ≤ L^m(G); and the upper bound L^m(G) ≤ 2 pw(G) + 2 for connected graphs, which is best possible up to a small additive constant.
Significance. If the results hold, they provide explicit and tight links between a contamination-clearing game parameter and the standard graph parameter pathwidth, with exact characterizations on trees and general bounds on arbitrary connected graphs. The monotonicity result for isometric subgraphs, the explicit counterexample, and the separation showing pw does not lower-bound L on general graphs are valuable for clarifying the behavior of the parameter. These contributions strengthen the understanding of pursuit-evasion games and their algorithmic implications.
minor comments (3)
- [Abstract] The abstract lists seven concrete results but provides no brief formal definition of the game rules, lion number, or contamination spreading; adding one sentence on the precise rules would improve readability for readers unfamiliar with the variant.
- [Tree results] In the statement of the tree bounds, clarify whether the upper bound L(T) ≤ pw(T)+1 is achieved by a specific strategy derived from a path decomposition and how recontamination is prevented during the clearing process.
- [Monotone variant] The claim that the monotone upper bound is 'best possible up to a small additive constant' should include a brief reference to the construction or family of graphs achieving near-tightness.
Simulated Author's Rebuttal
We thank the referee for their accurate summary of our results and for recommending minor revision. The report correctly identifies the key contributions, including the monotonicity property for isometric subgraphs, the tight characterization pw(T) ≤ L(T) ≤ pw(T)+1 for trees, the counterexample for non-isometric subgraphs, the fact that pw does not lower-bound L on general graphs, the upper bound L(G) ≤ pw(G)+1 for connected graphs, and the bounds pw(G) ≤ L^m(G) ≤ 2pw(G)+2 for the monotone variant.
Circularity Check
No significant circularity
full rationale
The paper derives inequalities relating lion number L(G), monotone lion number L^m(G), and pathwidth pw(G) via explicit proofs of monotonicity for isometric subgraphs, direct bounds for trees and general graphs, and counterexamples for non-isometric cases. None of the load-bearing steps reduce by construction to self-definitions, fitted inputs renamed as predictions, or self-citation chains; the results follow from the stated game rules and standard graph parameters without circular equivalence to inputs.
Axiom & Free-Parameter Ledger
axioms (1)
- domain assumption Finite undirected graphs with the standard definition of pathwidth and the lions-and-contamination spreading rule.
Reference graph
Works this paper leans on
-
[1]
Discrete Mathematics , volume=
Minimal acyclic forbidden minors for the family of graphs with bounded path-width , author=. Discrete Mathematics , volume=. 1994 , publisher=
work page 1994
-
[2]
Journal of Combinatorial Optimization , volume=
Zero-visibility cops and robber and the pathwidth of a graph , author=. Journal of Combinatorial Optimization , volume=. 2015 , publisher=
work page 2015
-
[3]
SIAM Journal on Discrete Mathematics , volume=
From pathwidth to connected pathwidth , author=. SIAM Journal on Discrete Mathematics , volume=. 2012 , publisher=
work page 2012
-
[4]
Research in Computational Topology 2 , pages=
Lions and contamination, triangular grids, and cheeger constants , author=. Research in Computational Topology 2 , pages=. 2022 , publisher=
work page 2022
-
[5]
Proceedings of the Twenty-Third Annual Symposium on Computational Geometry , pages =
Dumitrescu, Adrian and Suzuki, Ichiro and Zylinski, Pawel , title =. Proceedings of the Twenty-Third Annual Symposium on Computational Geometry , pages =. 2007 , isbn =. doi:10.1145/1247069.1247085 , abstract =
-
[6]
Berger, Florian and Gilbers, Alexander and Grüne, Ansgar and Klein, Rolf , TITLE =. Algorithms , VOLUME =. 2009 , NUMBER =
work page 2009
-
[7]
and Na, Hyeon-Suk and Shin, Chan-Su
Brass, Peter and Kim, Kyue D. and Na, Hyeon-Suk and Shin, Chan-Su. Escaping Off-Line Searchers and a Discrete Isoperimetric Theorem. Algorithms and Computation. 2007
work page 2007
-
[8]
Lions and contamination: Monotone clearings , journal =. 2023 , issn =. doi:https://doi.org/10.1016/j.comgeo.2022.101961 , author =
-
[9]
Graph minors. I. Excluding a forest , journal =. 1983 , issn =. doi:https://doi.org/10.1016/0095-8956(83)90079-5 , author =
-
[10]
Graph searching, path-width, tree-width and related problems (a survey) , author=. DIMACS Ser. in Discrete Mathematics and Theoretical Computer Science , volume=
-
[11]
Information Processing Letters , volume=
The vertex separation number of a graph equals its path-width , author=. Information Processing Letters , volume=. 1992 , publisher=
work page 1992
-
[12]
Theoretical computer science , volume=
A partial k-arboretum of graphs with bounded treewidth , author=. Theoretical computer science , volume=. 1998 , publisher=
work page 1998
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.