Graphs Simultaneously Achieving Three Vertex Cover Numbers

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^{\mathrm{\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}^{\mathrm{\infty }}(G)$. These three vertex cover parameters satisfy the relation $\alpha (G)\le {\alpha }_m^{\mathrm{\infty }}(G)\le {\alpha }_{mt}^{\mathrm{\infty }}(G)\le 2\alpha (G).$ We define a triple $(p,q,r)$ of positive integers such that $p\le q\le r\le 2p$ to be feasible if there is a connected graph $G$ such that $\alpha (G)=p$, ${\alpha }_m^{\mathrm{\infty }}(G)=q$, and ${\alpha }_{mt}^{\mathrm{\infty }}(G)=r$. This paper shows all triples with the above restrictions are feasible if $p\ne q$ or $r\le \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.