{"id":"arxiv/2609.39103","url":"https://arxiv.org/abs/2609.39103","tags":["math.CO","cs.DM"],"score":0,"title":"On Eternal Connected Vertex Cover","domain":"math.CO","source":"arxiv","authors":["Rajat Adak","Saraswati Girish Nanoti"],"reviews":0,"subject":"math.CO","summary":"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…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-09-30","reactions":{}}