Bounding the Eviction Number of a Graph in Terms of its Independence Number

Abstract

An eternal dominating family of graph $G$ in the eviction game is a collection ${\mathcal{D}}_k=\{D_1,...,D_l\}$ of dominating sets of $G$ such that (a) $|D_i|=|D_j|$ for all $i,j\in \{1,2,...,l\}$, and (b) for any $i\in \{1,2,...,l\}$ and any $v\in D_i$, either all neighbours of $v$ belong to $D_i$, or there are a neighbour $w$ of $v$ not in $D_i$ and an integer $j\in \{1,2,...,l\}\setminus \{i\}$ such that $D_i\cup \{w\}\setminus \{v\}=D_j$. The eviction number of $G$, denoted by $e^{\infty }(G)$, is the smallest cardinality of the sets in such an eternal dominating family. We compare $e^{\infty }$ to the independence number $\alpha$. We show that the ratio $\alpha /e^{\infty }$ is unbounded and construct an infinite class of connected graphs for which $e^{\infty }/\alpha \approx 4/3$. As our main result, we use Ramsey numbers to show that for any integer $k\ge 1$, there exists a function $f(k)$ such that any graph with independence number $k$ has eviction number at most $f(k)$.

16 pages, 3 figures