Mortal And Eternal Vertex Covers

Keywords

Death spiral number; Eternal protection; Independence system; Mortal vertex cover; Tree covers; 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 5, and α(G) is the cardinality of a smallest vertex cover. For a given vertex cover 5, a defense by S to an attack on an edge e = {vw}t where v ∈S, is a one-to-one function f: S→V, such that (1) f(v) =w, and (2) for each s ∈ S - v, f(s) ∈N[s]. Informally, a set is an eternal vertex cover if it can defend an "attack" on any edge and the process can be repeated indefinitely. The cardinality of a smallest eternal vertex cover is denoted α m∞ (G). A set of vertices which is not an eternal vertex cover is mortal. A formal definition of eternal vertex cover is provided and demonstrated to be equivalent to a characterization using closed families of vertex covers. Eternal vertex covers are shown to be closed under taking supersets and a lower bound for α m∞; (G) is given which depends on the vertex connectivity number and the independent domination number. A corresponding upper bound is given for the size of a mortal set. The death spiral number of a mortal vertex cover is defined and used to partition the collection of all mortal sets. Mortal sets are shown to be closed under taking subsets implying the collection of mortal sets for a graph with at least one edge is an independence system. The death spiral number of a graph is the maximum of the death spiral numbers of all mortal sets. An optimal attack/defense strategy is determined for a set of size α m∞ (T) -1 in a tree T, along with a polynomial labeling algorithm which computes its death spiral number.

Publication Date

11-1-2016

Publication Title

Journal of Combinatorial Mathematics and Combinatorial Computing

Volume

99

Number of Pages

3-21

Document Type

Article

Personal Identifier

scopus

Socpus ID

85010858424 (Scopus)

Source API URL

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

This document is currently not available here.

Share

COinS