Graphs Simultaneously Achieving Three Vertex Cover Numbers

Mark Anderson1, Julie R. Carrington1, Robert C. Brigham2, Ronald D.Dutton3, Richard P. Vitray1
1Department of Mathematics and Computer Science, Rollins College, Winter Park, FL 32789
2Department of Mathematics, University of Central Florida, Orlando, FL 32816
3Computer Science, University of Central Florida, Orlando, FL 32816

Abstract

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)\), and (4) \(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.

Keywords: vertex cover, total vertex cover, eternal, edge protection, graph characterization, domination, total domination.