#### Title

Graphs Simultaneously Achieving Three Vertex Cover Numbers

#### Keywords

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

#### Abstract

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

11-1-2014

#### Publication Title

Journal of Combinatorial Mathematics and Combinatorial Computing

#### Volume

91

#### Number of Pages

275-290

#### Document Type

Article

#### Personal Identifier

scopus

#### Copyright Status

Unknown

#### Socpus ID

84914704380 (Scopus)

#### Source API URL

https://api.elsevier.com/content/abstract/scopus_id/84914704380

#### STARS Citation

Anderson, Mark; Carrington, Julie R.; Brigham, Robert C.; Dutton, Ronald D.; and Vitray, Richard P., "Graphs Simultaneously Achieving Three Vertex Cover Numbers" (2014). *Scopus Export 2010-2014*. 8175.

https://stars.library.ucf.edu/scopus2010/8175