2026/07/25 by Jasine Babu, Pratik Ghosal, Cipriyano Simoes
#cs.DM
Eternal vertex cover problem is a graph protection problem which is a dynamic two player game variant of the classical vertex cover problem. In this game, the minimum number of guards required to protect a graph G is called the eternal vertex cover number of G, denoted by evc(G). It is known that for any graph G, mvc(G) ≤ evc(G) ≤ 2mvc(G), where mvc(G) is the vertex cover number of G, and that these bounds are generally tight. However, no biconnected graph G achieves evc(G) = 2mvc(G) and no better lower bounds are known for them. In this work, we focus on biconnected graphs in graph families. For infinite graph families F, consider the parameter ρ(F)=sup\r ∈ ℝ: for infinitely many graphs G ∈ F,(evc(G))/(mvc(G))≥ r\. No class of biconnected graphs F is known yet, for which 1 < ρ(F)<2. In this paper, we show that when F is the family of Halin graphs, (7)/(6) ≤ ρ(F) ≤ (3)/(2). Halin graphs are 3-connected and they have treewidth three. To show the lower bound, we construct a family of Halin graphs for which the ratio tends to (7)/(6) with increasing graph size. For the upper bound, we give two algorithms. Our first algorithm gives a defense strategy with (3)/(2) mvc(G) guards and serves as a (3)/(2) factor approximation algorithm to compute the eternal vertex cover number of Halin graphs. This algorithm also gives an upper bound of (4)/(3) for ρ for several subclasses of Halin graphs. Our second algorithm attains the upper bound of (4)/(3) for caterpillar Halin graphs. Whether computing eternal vertex cover number is NP-hard for Halin graphs remains an open problem, as is the case with treewidth two graphs.