Eternal Vertex Cover Problem on Halin Graphs

Abstract

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)\le evc(G)\le 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 $\mathcal{F}$, consider the parameter $\ddot{I}(\mathcal{F})=\sup \{r\in \mathbb{R}:\text{ for infinitely many graphs }G\in \mathcal{F},\frac{evc(G)}{mvc(G)}\ge r\}$. No class of biconnected graphs $\mathcal{F}$ is known yet, for which $1<\ddot{I}(\mathcal{F})<2$. In this paper, we show that when $\mathcal{F}$ is the family of Halin graphs, $\frac{7}{6}\le \ddot{I}(\mathcal{F})\le \frac{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 $\frac{7}{6}$ with increasing graph size. For the upper bound, we give two algorithms. Our first algorithm gives a defense strategy with $\frac{3}{2}mvc(G)$ guards and serves as a $\frac{3}{2}$ factor approximation algorithm to compute the eternal vertex cover number of Halin graphs. This algorithm also gives an upper bound of $\frac{4}{3}$ for $\ddot{I}$ for several subclasses of Halin graphs. Our second algorithm attains the upper bound of $\frac{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.