Source-linked AI summary
On Eternal Connected Vertex Cover
Rajat Adak, Saraswati Girish Nanoti
TL;DR
The paper asks when the minimum connected vertex cover size is enough to defend against every sequence of edge attacks. It develops structural criteria and applications, while showing that vertex membership alone does not ensure equality. A 32-vertex counterexample has cvc(G) = 19 and ecvc(G) = 20, and the paper characterizes a class where equality is equivalent to vertex membership and a cycle condition.
Problem
Whether every vertex belonging to some minimum connected vertex cover suffices for ecvc(G) = cvc(G) is an open question the paper addresses.
Source: §1 · p. 3Method
The paper proves a sharp bound and structural characterization for graphs with minimum degree at least two, then applies the criterion to full subdivisions and minimally 2-connected graphs.
Source: §1 · p. 3, §5.1 · p. 21Results
A 32-vertex graph has cvc(G) = 19 and ecvc(G) = 20 despite every vertex belonging to a minimum connected vertex cover; within the characterized class, equality is equivalent to vertex membership and at least two degree-two vertices on every cycle.
Source: §1 · p. 3Takeaways & Limitations
Within the characterized class, vertex membership in minimum connected vertex covers provides an exact test for equality, equivalent to the stated cycle condition.
Source: §1 · p. 3Membership in the equality class alone does not ensure ecvc(G) = cvc(G), as the diamond K4 − e demonstrates.
Source: §4.2 · p. 18
Abstract
from arXiv · showhide
For a connected graph $G$ with at least one edge, the \textit{eternal connected vertex cover} number $ecvc(G)$ is the minimum number of guards that can maintain a connected vertex cover after every response to an arbitrary sequence of edge attacks. Denote the minimum size of a connected vertex cover by $cvc(G)$. It is known that $cvc(G)\leq ecvc(G)\leq cvc(G)+1$. A necessary condition for $ecvc(G)=cvc(G)$ is that every vertex belongs to some minimum connected vertex cover. We show that this condition is not sufficient: there exists a $32$-vertex graph $G$ that has $cvc(G)=19$ and $ecvc(G)=20$, although every vertex of $G$ belongs to some minimum connected vertex cover. For connected graphs with minimum degree at least two, we establish the sharp bound $cvc(G)\geq 2|V(G)|-|E(G)|-1$ and $\mathcal F$ denotes the class attaining equality. We prove that $G\in\mathcal F$ if and only if the vertices of degree at least three induce a forest. Within $\mathcal F$, the conditions $ecvc(G)=cvc(G)$, membership of every vertex in some minimum connected vertex cover, and the presence of at least two degree-two vertices on every cycle are equivalent. As applications, we obtain $ecvc(G)=cvc(G)$ for full subdivisions of connected graphs of minimum degree at least two and for minimally $2$-connected graphs. In both the families, every minimum connected vertex cover is an eternally winning configuration. This is not true in general for graphs outside $\mathcal{F}$, we show one example of such a graph.
1 Introduction
The paper studies when the minimum connected vertex cover size suffices for eternal defense against edge attacks. It gives a counterexample to a natural membership criterion and identifies a structural class where that criterion does characterize equality.
1 Introduction
- The eternal connected vertex cover game requires guards to maintain a connected vertex cover after each response to an edge attack.The least number of guards that can defend every infinite attack sequence is ecvc(G).Source: §1 · p. 2
- For any connected graph with at least two vertices, cvc(G) ≤ ecvc(G) ≤ cvc(G) + 1.The lower bound follows because every guard configuration must be a connected vertex cover; one extra guard suffices by the described strategy.Source: §1 · p. 2
- A 32-vertex graph has cvc(G) = 19 and ecvc(G) = 20, although every vertex belongs to some minimum connected vertex cover.Thus, the necessary vertex-membership condition for equality is not sufficient.Source: §1 · p. 3
- For connected graphs with minimum degree at least two, the paper proves a sharp lower bound for cvc(G) and characterizes equality by requiring the vertices of degree at least three to induce a forest.Within this equality class, ecvc(G) = cvc(G) is equivalent to every vertex belonging to a minimum connected vertex cover and to every cycle containing at least two degree-two vertices.Source: §1 · p. 3
- The paper applies its criterion to full subdivisions and minimally 2-connected graphs, and outlines sections on the counterexample, its modification, structural characterization, and applications.It focuses on graphs of minimum degree at least two because with a degree-one vertex and more than one edge, the vertex-membership condition cannot hold.Source: §1 · p. 3
2 Insufficiency of the vertex-membership condition
The section constructs a graph where every vertex appears in a minimum connected vertex cover, yet no such cover supports an eternal defense with the minimum number of guards. The obstruction is that the available minimum covers cannot respond compatibly to attacks.
2 Insufficiency of the vertex-membership condition
- Every connected vertex cover must include all six support vertices, and every minimum one includes exactly one private vertex from each private triangle.At least three vertices are also required from each of Q ∪ Z and R ∪ U; the unique size-three covers of those induced subgraphs are Q and R, respectively.Source: §2 · pp. 4–5
- There are exactly four types of connected vertex covers of G of size 19, built from A ∪ C, one private neighbor per support vertex, and one of four combinations of Q, R, Z, and U.These types cover every vertex across the family, establishing the membership condition despite the failure of eternal defense.Source: §2 · p. 7
- Any initial 19-guard configuration that is not Type A is forced into Type A by an attack adjacent to z0, or the attacker wins immediately.Only Type A covers contain z0, so after the forced move any remaining connected vertex cover must be Type A.Source: §2 · p. 9
- From Type A, an attack on c1u0 cannot be answered: a legal response would require a Type C cover, which needs ten guards in X although at most nine can occupy X after one round.Here X comprises C, U, and the six private neighbors of C.Source: §2 · pp. 9–10
- For graph G, with 19 guards, an attacker can force a Type A configuration or win; after Type A, attacking edge c1u0 wins, so ecvc(G) ≠ cvc(G).Every vertex of G belongs to some minimum-sized vertex cover.Source: §2 · p. 10
3 Modification of the counterexample
The section removes the edge q1z13 from the counterexample to form G′. The modified graph has equal eternal and minimum connected vertex cover numbers, although not every minimum cover is eternally winning.
3 Modification of the counterexample
- Deleting the single edge q1z13 produces G′, for which ecvc(G′) = cvc(G′) = 19.The defender can defend every attack sequence using configurations of Types B, C, D, and E.Source: §3 · pp. 10, 13, 17
- G′ has five types of connected vertex covers of size 19: Types A, B, C, D, and E.Type E uses A ∪ C ∪ R ∪ Z1 and one private neighbor of each support vertex.Source: §3 · p. 12
- No Type A configuration of G′ is eternally winning: attacking c1u0 requires a Type C cover, which cannot be reached in one round.Type A allows at most nine guards in X after the attack, whereas Type C requires ten.Source: §3 · p. 17
4 A structural criterion for equality
The section identifies a structural setting where minimum connected vertex covers can support eternal play, then characterizes that setting by the graph’s high-degree vertices. Within it, eternal equality, vertex coverage by minimum covers, and a cycle condition coincide.
4.1 The tight counting class
- At the lower-bound equality case, every minimum connected vertex cover induces a tree, and every omitted vertex has degree two.These properties characterize the equality case of the bound for connected graphs with minimum degree at least two.Source: §4.1 · p. 17
4.2 Characterizing eternal equality
- The diamond K4 −e belongs to F but has ecvc(G) > cvc(G), because its unique minimum connected vertex cover offers no alternative response to an attack.Its two degree-three vertices form that unique minimum cover; an attack from an occupied vertex to an omitted vertex cannot be defended with two guards.Source: §4.2 · p. 18
- Within F, ecvc(G) = cvc(G), every vertex belongs to a minimum connected vertex cover, and every cycle contains at least two degree-two vertices are equivalent conditions.Whenever these conditions hold, every minimum connected vertex cover is an eternally winning configuration.Source: §4.2 · p. 18
- For an attack from a cover vertex to an omitted vertex, the response shifts guards along a path to exchange a degree-two vertex on the resulting cycle for the attacked vertex.The resulting set is another minimum connected vertex cover, so the strategy can be repeated from every such cover.Source: §4.2 · p. 19
4.3 Recognizing the extremal class
- For connected graphs with minimum degree at least two, G belongs to F if and only if the vertices of degree at least three induce a forest.This gives a graph-structural criterion for membership in the extremal class.Source: §4.3 · p. 20
5 Applications
The applications use the paper’s equality criterion in two complementary settings: full subdivision creates the needed degree-two structure, while minimally 2-connected graphs have it by a classical theorem. A subdivision of the counterexample illustrates how that structural change restores equality.
5.1 Full subdivisions
- ecvc(S(H)) = cvc(S(H)) = 2n0 −1 for every connected H with minimum degree at least two.Moreover, every minimum connected vertex cover of S(H) is eternally winning.Source: §5.1 · p. 21
- The covers built from spanning trees of H are minimum connected vertex covers, and every vertex of S(H) occurs in at least one such cover.They need not enumerate all minimum covers, particularly when H has degree-two vertices.Source: §5.1 · p. 21
5.2 Revisiting the counterexample after subdivision
- Unlike G0, S(G0) has independent degree-at-least-three vertices, and every cycle contains at least three new degree-two vertices, satisfying both parts of the positive criterion.For G0, cvc(G0) = 19 and ecvc(G0) = 20.Source: §5.2 · p. 22
5.3 Minimally 2-connected graphs
- For minimally 2-connected G, ecvc(G) = cvc(G) = 2n −m −1, and every minimum connected vertex cover is eternally winning.Plummer’s theorem supplies the cycle structure used by the equality criterion.Source: §5.3 · p. 23
6 Conclusion
The paper characterizes when the eternal and minimum connected vertex cover numbers agree, including a counterexample to a natural sufficient condition. It also applies the results to two graph families.
- Within the class attaining the sharp bound, equality is equivalent to every vertex belonging to some minimum connected vertex cover, or every cycle containing at least two degree-two vertices.The paper also gives a graph where the vertex-membership condition holds but equality fails.Source: §6 · p. 23
- Full subdivisions and minimally 2-connected graphs have exact formulas for their eternal connected vertex cover numbers.Source: §6 · p. 23
Declaration of generative AI use
The authors report using ChatGPT during manuscript preparation.
- The authors used ChatGPT to help develop the counterexample, identify minimally 2-connected graphs as an equality class, and improve the manuscript’s language and organization.They state that they reviewed and revised the AI-assisted material and take responsibility for the mathematical correctness and final content.Source: Declaration of generative AI use · p. 23