2026-07-23T19:20:14Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:25125 2026-02-09T08:06:30Z ddc:004 open_access

A Characterization of Spartan Graphs and New Lower Bounds for Eternal Vertex Cover Misra, Neeldhara Nanoti, Saraswati Girish Eternal Vertex Cover Vertex Cover König Graphs Spartan Graphs Matchings The eternal vertex cover game is played between an attacker and a defender on an undirected graph G. The defender identifies k vertices to position guards initially. The attacker, on their turn, attacks an edge e, and the defender must move a guard along e to defend the attack. The defender may move other guards as well, under the constraint that every guard moves at most once and to a neighboring vertex. The smallest number of guards required to defend attacks forever is called the eternal vertex cover number of G, denoted evc(G). For any graph G, evc(G) is at least mvc(G) (the vertex cover number of G). A graph is Spartan if evc(G) = mvc(G). It is known that a bipartite graph is Spartan if and only if every edge belongs to a perfect matching. We show that the only König graphs that are Spartan are the bipartite Spartan graphs. We also give new lower bounds for evc(G), generalizing a known lower bound based on cut vertices. We finally show a new matching-based characterization of all Spartan graphs. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Neeldhara Misra and Saraswati Girish Nanoti 2025 Is Part Of LIPIcs, Volume 360, 45th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FSTTCS.2025.45 urn:nbn:de:0030-drops-251250 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2025.45 eng https://creativecommons.org/licenses/by/4.0/legalcode