Graphs Simultaneously Achieving Three Vertex Cover Numbers


Domination; Edge protection; Eternal; Graph characterization; Total domination; Total vertex cover; Vertex cover


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 > 3p/2. The graphs with triple (p,p+ 1,2p) are characterized and issues related to the conjecture are discussed.

Publication Date


Publication Title

Journal of Combinatorial Mathematics and Combinatorial Computing



Number of Pages


Document Type


Personal Identifier


Socpus ID

84914704380 (Scopus)

Source API URL


This document is currently not available here.