Mortal and Eternal Vertex Covers

Abstract

A $vertexcover$ 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. For a given vertex cover $S$, a defense by $S$ to an attack on an edge $e=\{v,w\}$, where $v\in S$, is a one-to-one function $f:S\to V$, such that:

1. $f(v)=w$, and
2. for each $s\in S–v$, $f(s)\in N[s]$.

Informally, a set is an $eternalvertexcover$ 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 ${\alpha }_m^{\mathrm{\infty }}(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 ${\alpha }_m^{\mathrm{\infty }}(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 $deathspiralnumber$ 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 ${\alpha }_m^{\mathrm{\infty }}(T)–1$ in a tree $T$, along with a polynomial labeling algorithm which computes its death spiral number.