Graphs Simultaneously Achieving Three Vertex Cover Numbers

A vertex cover of a graph \( G = (V, E) \) is a subset \( S \subseteq V \) such that every edge is incident with at least one vertex in \( S \), and \( \alpha(G) \) is the cardinality of a smallest vertex cover. Let \( \mathcal{T} \) be a collection of vertex covers, not necessarily minimum. We say \( \mathcal{T} \) is closed if for every \( S \in \mathcal{T} \) and every \( e \in E \) there is a one-to-one function \( f : S \to V \) such that

1. \( f(S) \) is a vertex cover,
2. for some \( s \in S \), \( \{s, f(s)\} = e \),
3. for each \( s \) in \( S \), either \( s = f(s) \) or \( s \) is adjacent to \( f(s) \),

\item \( f(S) \in \mathcal{T} \).

A set is an eternal vertex cover if and only if it is a member of some closed family of vertex covers. The cardinality of a smallest eternal vertex cover is denoted \( \alpha_m^\infty(G) \). Eternal total vertex covers are defined similarly, with the restriction that the cover must also be a total dominating set. The cardinality of a smallest eternal total vertex cover is denoted \( \alpha_{mt}^\infty(G) \). These three vertex cover parameters satisfy the relation

\[
\alpha(G) \leq \alpha_{m}^\infty(G) \leq \alpha_{mt}^\infty(G) \leq 2\alpha(G).
\]

We define a triple \( (p, q, r) \) of positive integers such that \( p \leq q \leq r \leq 2p \) to be feasible if there is a connected graph \( G \) such that \( \alpha(G) = p \), \( \alpha_{m}^\infty(G) = q \), and \( \alpha_{mt}^\infty(G) = r \). This paper shows all triples with the above restrictions are feasible if \( p \neq q \) or \( r \leq \frac{3p}{2} \) and conjectures that there are no feasible triples of the form \( (p, p, r) \) with \( r > \frac{3p}{2} \). The graphs with triple \( (p, p + 1, 2p) \) are characterized and issues related to the conjecture are discussed.