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

Socpus ID

84914704380 (Scopus)

Source API URL

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

This document is currently not available here.

Share

COinS