Graphs Simultaneously Achieving Three Vertex Cover Numbers

A vertex cover of a graph G = (V, E) is a subset S ⊆ V such that every edge is incident with at least one vertex in S, and α(G) is the cardinality of a smallest vertex cover. Let T be a collection of vertex covers, not necessarily minimum. We say T is closed if for every S ∈ T and every e ∈ E there is a one-to-one function f: S → 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(a), and (4) f(S) ∈ 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 α∞m(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 α∞mt(G). These three vertex cover parameters satisfy the relation α(G) ≤ α∞m(G) ≤ α∞mt(G) ≤ 2α(G). We define a triple (p,q,r) of positive integers such that p ≤ q ≤ r ≤ 2p to be feasible if there is a connected graph G such that α(G) = p, α∞m(G) = q, and α∞mt(G) = r. This paper shows all triples with the above restrictions are feasible if p ≠ q or r ≤ 3p/2 and conjectures that there are no feasible triples of the form (p,p,r) with r \u3e 3p/2. The graphs with triple (p,p+ 1,2p) are characterized and issues related to the conjecture are discussed