On Eternal Connected Vertex Cover
Abstract
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)≤ ecvc(G)≤ 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)≥ 2|V(G)|−|E(G)|−1 and ℱ denotes the class attaining equality. We prove that G∈ℱ if and only if the vertices of degree at least three induce a forest. Within ℱ, 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 ℱ, we show one example of such a graph.
Related
- Structural Parameterizations for Eternal Vertex Cover
- Weak and strong Lefschetz properties for vertex cover Artinian algebras associated to graphs
- Energy of signed graphs and the vertex cover number
- On Hamilton cycles in connected vertex-transitive graphs of order 2pq
- Bounds for the Vertex Chromatic Number of Connected Triangle-Free Graphs
BibTeX
@misc{adak2026eternal,
title = {{On Eternal Connected Vertex Cover}},
author = {Rajat Adak and Saraswati Girish Nanoti},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.39103},
eprint = {2609.39103},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.39103},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - On Eternal Connected Vertex Cover
AU - Rajat Adak
AU - Saraswati Girish Nanoti
PY - 2026
DA - 2026/09/30
PB - arXiv
DO - 10.48550/arxiv.2609.39103
UR - https://arxiv.org/abs/2609.39103
AB - 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)≤ ecvc(G)≤ 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)≥ 2|V(G)|−|E(G)|−1 and ℱ denotes the class attaining equality. We prove that G∈ℱ if and only if the vertices of degree at least three induce a forest. Within ℱ, 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 ℱ, we show one example of such a graph.
ER -