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\geq1\), there exists a function \(f(k)\) such that any graph with independence number \(k\) has eviction number at most \(f(k)\).
1 Introduction↩︎
Graph protection involves the placement of mobile sensors on the vertices of a graph \(G\) to protect the vertices and edges of \(G\) against either single or longer sequences of “events”occurring at the vertices or edges. We refer to these sensors as guards, and to the events as attacks. A guard located on a vertex \(v\) of a graph \(G\) covers \(v\) and all the neighbours of \(v\); we say that \(v\) is occupied (by a guard). A vertex without a guard is said to be unoccupied. The initial challenge is to find a (usually smallest) subset \(S\) of occupied vertices of \(G\) such that every vertex of \(G\) is either in \(S\) or adjacent to a vertex in \(S\), i.e., a dominating set of \(G\). However, real-world systems seldom remain static. As situations evolve, the once optimal dominating set of guards may face unforeseen challenges. Imagine a situation where a sensor must be moved from its original position due to maintenance needs, adverse weather conditions, or other complications. The challenge then becomes:
“How do we reposition this sensor without compromising the overall coverage?”
This is the point where the movement of guards becomes relevant. We restrict our investigation to attack sequences of arbitrary length. Each such problem, called an eternal domination problem, can be modelled as a two-player game, alternating between a defender and an attacker: the defender chooses the initial configuration of guards as well as each configuration following an attack, and the attacker chooses the locations of the attack. We further restrict our attention to the eviction game, which was introduced by Klostermeyer, Lawrence and MacGillivray in [1].
In the eviction game, only vertices containing a guard may be attacked. In the standard version of the eviction game, which we will simply refer to as eviction, the guards start by choosing their opening configuration, which must induce a dominating set. We consider the case where at most one guard is located on each vertex. At each turn the attacker selects a vertex \(v\) on which there is a guard and the guard on \(v\) responds by moving to an unoccupied neighbour; that is, a neighbour of \(v\) on which there is no guard, if possible. If each of the neighbours of \(v\) is occupied, then we say that \(v\) is surrounded, and the guard on \(v\) must stay put and cannot contribute to the dominating set for a time unit. We sometimes say that an attacked guard is evicted. Only the guard that is attacked is allowed to move to a neighbour. The guards win the game if they are able to maintain a dominating set in the graph after responding to each attack; otherwise, the attacker wins. Assuming the guards move optimally, an eternal dominating set of a graph \(G\) (in the eviction game) is any opening configuration (a dominating set of \(G\)) from which they can defend any sequence of attacks on \(G\). The eviction number of a graph \(G\), denoted by \(e^\infty(G)\), is the minimum cardinality of an eternal dominating set of \(G\) in the eviction game.
We focus on comparing the eviction number of \(G\) to its independence number \(\alpha(G)\). As we show in Section 2, it is easy to see that the ratio \(\alpha/e^{\infty}\) is unbounded. On the other hand, it is not so easy to determine whether the ratio \(e^{\infty}/\alpha\) is bounded or not. The cycle \(C_{7}\) is an example of a graph whose eviction number exceeds its independence number: \(\alpha(C_{7})=3\) and \(e^{\infty}(C_{7})=4\). We construct an infinite class of connected graphs for which \(e^{\infty }/\alpha \approx 4/3\). One of the difficulties one encounters when studying eviction is the anomaly that \(e^{\infty}\) could increase upon the addition of an edge. We illustrate this in Section 3. As our main result, we show in Section 4 that, for any integer \(k\geq1\), there exists a function, which we denote by \(f(k)\), such that any graph with independence number \(k\) has eviction number at most \(f(k)\). We state some open problems in Section 5.
2 Definitions and Background↩︎
Concepts not defined here can be found in any standard text on graph theory, e.g. [2], [3]. For further background on graph protection, see [4], [5].
For any positive integers \(n\) and \(k\), let \([n]\) denote the set \(\{1,2,...,n\}\) and let \(\binom{[n]}{k}\) denote the set of \(k\)-subsets of \([n]\).
We consider finite simple graphs and, as usual, denote the vertex and edge sets of a graph \(G\) by \(V(G)\) and \(E(G)\), respectively. The open neighbourhood of \(v\in V(G)\), denoted by \(N(v)\), is the set of vertices that are adjacent to \(v\). These vertices are known as the neighbours of \(v\). The closed neighbourhood of \(v\) is the set \(N[v]=N(v)\cup\{v\}\).
The disjoint union of a graph \(G\) and a graph \(H\), denoted by \(G+H\), is the graph with vertex set \(V(G) \cup V(H)\) and edge set \(E(G) \cup E(H)\). We denote the disjoint union of \(k\) disjoint copies of a graph \(G\) by \(k G\). The join of a graph \(G\) and a graph \(H\), denoted by \(G \vee H\), is the graph with vertex set \(V(G) \cup V(H)\) and edge set \(E(G) \cup E(H) \cup \{uv: u \in V(G), v \in V(H)\}\).
As stated above, we denote the independence number of \(G\) by \(\alpha(G)\). Furthermore, we denote the clique number of \(G\) by \(\omega(G)\), the domination number by \(\gamma(G)\), the chromatic number by \(\chi(G)\), and the clique covering number (the minimum cardinality of a partition of \(V(G)\) such that each set in the partition induces a clique) by \(\theta(G)\). Observe that \(\alpha(G)=\omega(\overline{G})\) and \(\chi(G)=\theta(\overline{G})\) for any graph \(G\).
Let \(\mathcal{D}_{k}\) be the collection of all dominating sets of \(G\) of fixed cardinality \(k\). For \(D\in\mathcal{D}_{k}\), we imagine that there is a single guard located on each vertex of \(D\) and therefore we think of \(D\) as a configuration of guards. We say that a (not necessarily dominating) set \(X\) protects a vertex \(v\), or \(v\) is protected (by \(X\)), if \(v\) or one of its neighbours is occupied by a member of \(X\).
As explained in the introduction, each eternal domination problem can be modelled as a two-player game, alternating between a defender and an attacker: the defender chooses \(D_{1}\in\mathcal{D}_{k}\) as well as each \(D_{i}\), \(i>1\), while the attacker chooses the locations \(r_{1},r_{2},\ldots\) of the attacks; we say the attacker attacks the vertices \(r_{i}\). Thus, the game starts with the defender choosing \(D_{1}\). For \(i\geq1\), the attacker attacks \(r_{i}\) and the defender defends against the attack by choosing \(D_{i+1}\in\mathcal{D}_{k}\) subject to constraints that depend on the particular game. The defender wins the game if they can successfully defend the graph against any sequence of attacks, including sequences that are infinitely long, subject to the constraints of the game; the attacker wins otherwise. In other words, the attacker’s goal is to force the defender into a configuration of guards that is not dominating. These dynamic models of domination were first defined and studied by Burger, Cockayne, Gründlingh, Mynhardt, Van Vuuren and Winterbach in [6], [7]. In particular, they studied the eternal domination number \(\gamma^\infty(G)\) of a graph \(G\), which is the smallest number of guards that can defend \(G\) against arbitrary sequences of attacks on unguarded vertices, where a single guard must move to the attacked vertex.
The definitions below of eternal dominating families of a graph in the eternal domination and the eviction games illustrate the difference between the two protection models.
An eternal dominating family of a graph \(G\) (in the eternal domination game) is a collection of sets \(D_1, D_2, D_3, \ldots, D_l\) of \(G\) that satisfy the following properties.
For any \(i, j \in [l]\), \(|D_i|=|D_j|\).
For any \(i \in [l]\) and any \(w \in V(G)-D_i\), there exist \(v \in D_i \cap N(w)\) and \(j \in [l]-\{i\}\) such that \((D_i \cup \{w\})-\{v\} = D_j\).
An eternal dominating family of a graph \(G\) (in the eviction game) is a collection of dominating sets \(D_{1},D_{2},D_{3},\ldots,D_{l}\) of \(G\) that satisfy the following properties.
For any \(i, j \in[l]\), \(|D_{i}|=|D_{j}|\).
For any \(i\in\lbrack l]\) and any \(v\in D_{i}\), either \(N[v]\subseteq D_{i}\), or there exist \(w\in N(v)-D_{i}\) and \(j\in\lbrack l]-\{i\}\) such that \(D_{i}\cup\{w\}-\{v\}=D_{j}\).
Item (2) implies that the \(D_i\) are dominating sets whereas (4) does not; thus we have to specify this explicitly. We proceed by stating some results on eviction obtained by Klostermeyer, Lawrence and MacGillivray in [1].
Proposition 1 ([1]). If \(k < |V(G)|\) guards can defend an arbitrarily long sequence of attacks in the eviction game on a graph \(G\), then so can \(k+1\) guards.
We now examine how the eviction number of a graph \(G\) relates to some other parameters such as the domination number, the independence number and the clique covering number of \(G\).
Proposition 2 ([1]). For any graph \(G\), \(\gamma(G) \leq e^\infty(G) \leq \theta(G)\).
Since \(\alpha(G)\) is a lower bound on \(\gamma^\infty(G)\) (see [7]) and belongs to the interval \([\gamma(G), \theta(G)]\), it is reasonable to ask whether \(\alpha(G)\) is also a lower bound on \(e^\infty(G)\). Observation 4 shows that this is not the case. Indeed, while fixing \(e^\infty(G)=1\), \(\alpha(G)\) can be arbitrarily large. Hence the ratio \(\alpha/e^\infty\) is unbounded.
Proposition 3. Let \(G\) be a graph with at least two universal vertices. Then \(\left. e^{\infty }(G)=1\right..\)
Proof. Let \(u, v\) be two universal vertices of \(G\). By moving back and forth on the vertices \(u\) and \(v\), one guard can dominate all of the vertices of \(G\) at each time \(t=1,2,3,\ldots.\) ◻
Observation 4. Let \(G\) be the join of the graph \(K_2\) with the graph \(\overline{K_m}\) \((\)see Figure \(\ref{Figure:EvictionNumberOne})\). Then \(\alpha(G)=m\) and \(e^\infty(G)=1\).
It is not so easy to determine whether the ratio \(e^{\infty}/\alpha\) is bounded or not. The cycle \(C_{7}\) is an example of a graph with \(\alpha=3\) and \(e^{\infty}=4\). Therefore, disjoint unions of \(C_{7}\) provide infinitely many (disconnected) graphs \(G\) for which \(e^{\infty}(G)/\alpha(G)=\frac{4}{3}\). To see that a similar result holds for connected graphs, consider the graph \(G_k\) obtained by joining a new vertex \(v\) to each vertex of \(kC_7\), and a new vertex \(w\) to \(v\) (see Figure 2 for the case where \(k=2\)). The graph \(G_k\) satisfies the properties described in the following proposition.
Proposition 5. For any \(k \geq 1\), \(\alpha(G_k)=3k+1\) and \(e^\infty(G_k)=\theta(G_k)=4k+1\).
Proof. The reader can easily verify that \(\alpha(G_k)=3k+1\) and \(\theta(G_k)=4k+1\). So, by Proposition 2, we only need to show that \(e^\infty(G_k) \geq 4k+1\). Suppose the assumption is false. Then \(G_k\) can be defended by \(4k\) guards (by Proposition [Proposition:EvictionMoreGuards]). Consider a configuration of these \(4k\) guards on \(G_k\). If \(w\) is occupied and \(v\) is unoccupied, then evict the guard on \(w\) to \(v\). Otherwise, \(v\) and \(w\) are both occupied; in this case, evict the guard on \(v\) to an unoccupied vertex of one of the copies of \(C_7\) and then evict the guard on \(w\) to \(v\). So, we may assume without loss of generality that \(v\) is occupied and \(w\) is unoccupied. Since there are \(4k\) guards located on \(G_k\), there is a copy of \(C_7\), which we will refer to as \(C_7^*\), on which are located fewer than four guards. Evict the guards located on \(C_7^*\) in a way such that a vertex of \(C_7^*\) is not dominated by any guard located on a vertex of this subgraph. Now, evict the guard located on \(v\). If the guard moves to \(w\), then a vertex of \(C_7^*\) is not dominated. If the guard moves somewhere else, then \(w\) is not dominated. This contradicts our assumption that \(4k\) guards can defend the graph. ◻
However, \(\alpha(G)\) is a lower bound on \(e^\infty(G)\) when \(G\) belongs to a specific graph class, as stated below.
Proposition 6 ([1]). If \(G\) is a triangle-free graph, then \(e^\infty(G) \geq \alpha(G)\).
We now give the values of \(e^\infty\) for paths, cycles and complete bipartite graphs.
Proposition 7 ([1]). For any integers \(n, m \geq 1\),
\(e^\infty(P_n)=\lceil \frac{n}{2} \rceil\),
\(e^\infty(C_3)=1\), \(e^\infty(C_5)=2\) and \(e^\infty(C_n)=\lceil \frac{n}{2} \rceil\) for any \(n \neq 3, 5\),
\(e^\infty(K_{m, n})=\max \{m, n\}\).
Although \(\alpha(G)\) is neither an upper bound nor a lower bound on \(e^\infty(G)\), Klostermeyer and MacGillivray show that \(e^\infty(G)\) is bounded for the first three values of \(\alpha\).
Theorem 8 ([1]). If \[\alpha(G)=\left\{ \begin{tabular} [c]{l}1\\ 2\\ 3\end{tabular} \right. \text{,\;then\;}e^{\infty}(G)\left\{ \begin{tabular} [c]{l}=1\\ \leq2\\ \leq5.\end{tabular} \right.\]
It is unknown whether there exists a graph \(G\) such that \(\alpha(G)=3\) and \(e^{\infty}(G)=5\). There are also no results in the literature bounding the eviction number in terms of the independence number when the latter is at least \(4\).
Klostermeyer and MacGillivray [8] proved that \(\gamma^{\infty}(G)\leq\binom{\alpha(G)+1}{2}\) for any graph \(G\). Thus, the eternal domination number of a graph is bounded by a function of its independence number. Since no such bound is known in general for the eviction number of the graph, Klostermeyer, Lawrence and MacGillivray asked the following questions.
Question 1 ([1]). Does there exist a constant \(c\) such that \(e^\infty(G) \leq c \alpha(G)\) for all graphs \(G\)?
Question 2 ([1]). Does there exist a graph \(G\) such that \(\gamma^\infty(G)<e^\infty(G)\)?
The results in the next two sections are motivated by Question 1, which still remains unanswered. We aim to show the existence of a function \(f\) such that any graph with independence number \(k\) has eviction number at most \(f(k)\). We begin by illustrating one of the difficulties we encountered when trying to determine the eviction number of a graph by considering its subgraphs.
3 Eviction is Different↩︎
For almost any domination-type parameter \(\pi\), adding an edge to a graph \(G\) can only result in a graph \(G^{\prime}\) with \(\pi(G^{\prime}) \leq \pi(G)\), and usually \(\pi(G^{\prime}) \in \{\pi(G), \pi(G)-1\}\). This is not the case with the eviction number.
Consider the graph \(G \cong K_{1} + (K_{2} \vee \overline{K_{t}}),t\geq2\). Observe that \(G\) has eviction number \(2\) and the graph \(G'\) obtained from \(G\) by adding an edge from the isolated vertex of \(G\) to one of the vertices of degree \(t+1\) has eviction number \(t+1\). The problem occurs when the attacker can force a guard to be surrounded.
This is trivially the case for \(K_{1}\), but there are infinitely many graphs with this property. For example, the spider \(\operatorname{Sp}(2;k)\), which is obtained from the star \(K_{1,k}\) by subdividing each edge exactly once, has eviction number \(k+1\). The attacker can force guards to be on the central vertex \(c\) and all its neighbours. Now, when \(c\) is joined to a vertex of another graph, for example \(K_{2}\vee\overline{K_{t}}\) (and again there are infinitely many examples), the eviction number of the resulting graph can be arbitrarily higher than the eviction number of \(\operatorname{Sp}(2;k) + (K_{2}\vee\overline{K_{t}})\) (see Figure [Figure:EvictionEdgeAdditionRemovalDisconnected]).
The graph \(G_2\) in Figure [Figure:EvictionEdgeAdditionRemovalConnected] is an example of a connected graph for which adding an edge increases the eviction number. In fact, three guards can defend the subgraph induced by the vertices \(v_0, v_2, v_2', v_2'', v_2'''\) using the same strategy from the previous paragraph while one guard defends the subgraph induced by the vertices \(v_1, v_1', v_1'', v_1'''\). However, the graph \(G_2'\) obtained from \(G_2\) by the addition of the edge \(v_0v_1\) cannot be defended by four guards. To see this, suppose four guards are initially located on the vertices of \(G_2'\). We may assume without loss of generality that the vertex \(v_0\) is occupied since its neighbourhood is an independent set. We may further assume without loss of generality that there are two guards located on \(v_2\) and \(v_2'\), and one guard located on \(v_1'\). After the sequence of attacks \(v_0, v_1', v_1, v_2', v_2\), a vertex of \(G_2'\) is not dominated.
A graph may have several vertices on which guards are surrounded at the same time. By Proposition 7, the complete bipartite graph \(K_{r, r+s}\), where \(s>0\), has eviction number \(r+s\). The attacker can force \(r\) guards to be located on the vertices of degree \(r+s\) and \(s\) guards to be located on the vertices of degree \(r\); these \(s\) guards are all surrounded.
The above paragraphs illustrate that, when determining the eviction number of a graph \(G\) by considering how guards can defend various subgraphs of \(G\), it may be important to establish that the guards can always move within these specific subgraphs.
4 The Function \(f\)↩︎
We begin our result on the function \(f\) with the following definition.
The Ramsey number \(r(k, l)\) is the minimum integer \(n\) such that any graph on at least \(n\) vertices contains either an independent set of size \(k\) or a clique of size \(l\).
The special case of Ramsey’s Theorem [9] applied to a graph and its complement ensures that the Ramsey number \(r(k, l)\) is well defined. We use this theorem to prove the following lemma on which the proof of our main theorem depends.
Lemma 1. For any integer \(k \geq 1\), there exists a constant \(c(k)=c_k\) such that if \(G\) is a graph with independence number \(k\) which has at least \(c_k\) disjoint maximum independent sets, then \(G\) can be defended by \(k^2\) guards. Moreover, no guard is ever prevented from moving by being surrounded.
Proof. Let \(k \geq 1\) and let \(l_0, l_1, l_2, l_3, \ldots, l_k\) be sufficiently large positive integers (which will be chosen later). Let \(G\) be a graph with independence number \(k\). Suppose \(G\) has at least \(c_k = l_0\) disjoint maximum independent sets \(R_1, R_2, R_3, \ldots, R_{c_k}\), where \(R_i=\{v_{i,1}, v_{i,2}, v_{i,3}, \ldots, v_{i,k}\}\) for each \(i=1,2,3,\ldots,c_k\).
If \(l_0 \geq r(k+1, l_1)\), Ramsey’s Theorem guarantees that there exist \(l_1\) vertices in the set \(\bigcup_{i \in [l_0]} \{v_{i,1}\}\) which induce a complete subgraph of \(G\). Without loss of generality, let \(C_1=\{v_{1,1}, v_{2,1}, v_{3,1}, \ldots, v_{l_1,1}\}\) be such a set. If \(l_1 \geq r(k+1, l_2)\), Ramsey’s Theorem guarantees that there exist \(l_2\) vertices in the set \(\bigcup_{i \in [l_1]} \{v_{i,2}\}\) which induce a complete subgraph of \(G\). Without loss of generality, let \(C_2=\{v_{1,2}, v_{2,2}, v_{3,2}, \ldots, v_{l_2,2}\}\) be such a set. Likewise, for each \(j \in \{3, 4, \ldots, k-1\}\), if \(l_{j-1} \geq r(k+1, l_j)\), Ramsey’s Theorem guarantees that there exist \(l_j\) vertices in the set \(\bigcup_{i \in [l_{j-1}]} \{v_{i,j}\}\) which induce a complete subgraph of \(G\). Finally, if \(l_{k-1} \geq r(k+1, k+1)\), then there exist \(l_k = k+1\) vertices in the set \(\bigcup_{i \in [l_{k-1}]} \{v_{i,k}\}\) which induce a complete subgraph of \(G\). To summarize, let:
\[\begin{align} {3} & l_k &&= k+1 \\ & l_{k-1} &&= r(k+1, l_k) &&= r(k+1, k+1) \\ & l_{k-2} &&= r(k+1, l_{k-1}) &&= r(k+1, r(k+1, k+1)) \\ &&\vdots \\ & l_0 &&= r(k+1, l_1) &&= \underbrace{r(k+1, r(k+1, r(k+1, \ldots)))}_{\text{k times}}. \end{align}\]
As explained above, if \(G\) has at least \(c_k = l_0\) disjoint independent sets of size \(k\), then \(G\) has a subset of vertices \(S^*=\bigcup_{i \in [k+1], j \in [k]} \{v_{i,j}\}\), where:
\(R_i = \bigcup_{j \in [k]} \{v_{i,j}\}\) is a maximum independent set for each \(i \in [k+1]\),
\(C_j' = \bigcup_{i \in [k+1]} \{v_{i,j}\}\) is a clique of size \(k+1\) for each \(j \in [k]\).
We can represent \(S^*\) as an array with rows \(R_i, i \in [k+1]\), and columns \(C_j', j \in [k]\), as below:
\[\begin{bmatrix} v_{1,1} & v_{1,2} & v_{1,3} & \cdots & v_{1,k} \\ v_{2,1} & v_{2,2} & v_{2,3} & \cdots & v_{2,k} \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ v_{k+1,1} & v_{k+1,2} & v_{k+1,3} & \cdots & v_{k+1,k} \end{bmatrix}.\]
In this case, place \(k\) guards in \(C_j'\) for each \(j \in [k]\) so that the subset \(S^*\) contains exactly \(k^2\) vertices. For any \(j \in [k]\), if a guard in \(C_j'\) is attacked, the guard can always relocate to the only unoccupied vertex in \(C_j'\). Since there are exactly \(k+1\) rows \(R_1, R_2, R_3, \ldots, R_{k+1}\) and there are exactly \(k^2\) guards located in \(S^*=\bigcup_{i \in [k+1]} R_i\) at each time \(t=1,2,3,\ldots\), by the Generalized Pigeonhole Principle, there is an integer \(m \in [k+1]\) such that row \(m\) contains at least \(\lceil \frac{k^2}{k+1} \rceil=k\) guards; that is, all the vertices in \(R_m\) are occupied. Since \(R_m\) is a maximum independent (and hence dominating) set of \(G\), all the vertices in \(G\) are dominated by \(R_m\). This completes the proof. ◻
Observe that our proof of Lemma 1 shows that \(c_1 \leq r(2,2)=2\) and \(c_2 \leq r(3, r(3,3))=18\).
We are now ready to prove our main theorem.
Theorem 9. There exists a function \(f\) such that if \(G\) is a graph with independence number \(k\geq1\), then \(e^{\infty}(G)\leq f(k)\). In particular, \[f(1)=1\text{\;and}\;f(k)\leq\frac{2kc_{k}(k^{k-1}-1)}{k-1}\;\text{when}\;k\geq2,\] where \(c_{k}\) is as in Lemma 1.
Proof. The cases \(k=1, 2, 3\) are clear (see Theorem 8). Let \(G\) be a graph such that \(\alpha(G) = k \geq 4\). We may assume that \(|V| > f(k)\); otherwise, the theorem clearly holds for \(G\).
If \(G\) has at least \(c_k\) disjoint independent sets of size \(k\), then, by Lemma 1, \(G\) can be defended by \(k^2\) guards. So, we may further assume that \(G\) has fewer than \(c_k\) disjoint maximum independent sets. We first prove the following claim:
Claim 10. There exist a positive integer \(l < k\) and a subset \(S\) of vertices of \(G\) such that \(\alpha(G-S)=l\) and \(G-S\) has at least \(c_l + |S|\) disjoint independent sets of size \(l\).
Proof. Let \(G_0, G_1, G_2, \ldots, G_{k-1}\) be a sequence of subgraphs of \(G\) (where \(G=G_0\)) that satisfy the following conditions for each \(i \in \{0, 1, 2, \ldots, k-2\}\):
\(\alpha(G_i) = k-i\).
\(G_{i+1} = G_i - S_i\), where \(S_i\) is a smallest subset of vertices of \(G_i\) such that \(\alpha(G_i-S_i)= k-i-1\).
Since \(G_0\) has fewer than \(c_k\) disjoint independent sets of cardinality \(k\), we have \(|S_0| < k c_k\).
If \(G_{1}\) has at least \(c_{k-1}+|S_{0}|\) disjoint independent sets of cardinality \(k-1\), then we are done, hence suppose this is not the case. Then \[|S_{1}| < (k-1)(c_{k-1}+|S_{0}|) < (k-1)(c_{k-1}+k c_k) < k^2 c_k.\]
If \(G_{2}\) has at least \(c_{k-2}+|S_0|+|S_1|\) disjoint independent sets of cardinality \(k-2\), then we are done, hence suppose this is not the case. Then \[|S_{2}| < (k-2)(c_{k-2}+|S_0|+|S_1|) < (k-2)(c_{k-2}+k c_k+k^2 c_k) < k^3 c_k.\]
Likewise, for each \(i \in \{3, 4, 5, \ldots, k-2\}\), if \(G_{i}\) has at least \(c_{k-i}+|S_0|+|S_1|+\cdots+|S_{i-1}|\) disjoint independent sets of cardinality \(k-i\), then we are done, hence suppose this is not the case. Then \[\begin{align} |S_{i}| & < (k-i)(c_{k-i}+|S_0|+|S_1|+\cdots+|S_{i-1}|) \\ & < (k-i)(c_{k-i} + k c_k + k^2 c_k + \cdots + k^i c_k) \\ & < k^{i+1} c_k. \end{align}\]
Since \(G\) is a graph of order at least \(1 + \frac{2 k c_k (k^{k-1}-1)}{(k-1)}\), \(G\) has a subset \(S = \bigcup_{i=0}^{k-2} S_i\) of cardinality at most \[\begin{align} |S_0|+|S_1|+\cdots+|S_{k-2}| & < c_k (k + k^2 + k^3 + \ldots + k^{k-2} + k^{k-1}) \\ & = \frac{k c_k (k^{k-1}-1)}{k-1} \end{align}\] such that \(G-S\) is a graph on at least \(1+|S|\) vertices with independence number \(1\). This completes the proof of the claim. ◻
Now, consider a smallest such subset of vertices \(S\) such that \(\alpha(G-S)=l < k\) and \(G-S\) has at least \(c_l + |S|\) disjoint independent sets of size \(l\).
Let \(M\) be a smallest matching in \(G\) that covers the largest number of vertices in \(S\). Let \(S'\) be the set of vertices in \(G-S\) that belong to an edge of the matching \(M\). Since \(|S'| \leq |S|\), \(\alpha(G-(S \cup S'))=l\) and \(G-(S \cup S')\) has at least \(c_l\) disjoint independent sets of size \(l\). As a consequence of Lemma 1, \(l^2\) guards (and therefore at most \(k^2\) guards) can defend \(G-(S \cup S')\) and any guard that is evicted can always move to an unoccupied vertex in that subgraph.
Since \(|S \cup S'| < \frac{2 k c_k (k^{k-1}-1)}{k-1}\), in the rest of the proof, we will show that there exists a strategy with no more than \(\frac{k c_k (k^{k-1}-1)}{k-1}\) guards to defend \(G'\), the subgraph of \(G\) induced by \(S \cup S'\), where it is always possible for any guard located on \(G'\) to move at each step of the game to a vertex of \(G'\). Let the initial configuration of the guards be such that there is exactly one guard on each edge of \(M\) and one guard on each vertex that is not covered by \(M\), where such a vertex necessarily belongs to \(S\). We will maintain the invariant that there is a guard on exactly one vertex of each edge of a matching \(M\) that covers the largest number of vertices of \(G'\) and one guard on each of the vertices that are not covered by the matching. The invariant is clearly initially satisfied. Suppose at some time \(t=1,2,3,\ldots\) a guard located on \(x_i\), a vertex that is covered by \(M\), is attacked. Observe that the guard located on \(x_i\) has at least one unoccupied neighbour \(y_i\), which is matched to \(x_i\) by \(M\), since there is only one guard on each edge of the matching. Move the guard to its neighbour \(y_i\). The invariant obviously still holds. Now, suppose a guard located on a vertex \(z_i\) in \(G'\) that is not covered by \(M\) is attacked. Note that our choice of \(M\) implies that \(z_i \in S\). We consider two cases:
Case \(1\): If \(z_i\) has no unoccupied neighbour in \(G\), then there is nothing to do.
Case \(2\): If \(z_i\) has an unoccupied neighbour \(x_i\), then \(x_i\) is covered by \(M\) and therefore belongs to \(G'\); otherwise we could find a matching that covers more vertices of \(S\). Then, there exists \(y_i \in S\) such that \(x_i\) is matched to \(y_i\) by \(M\) and there is a guard on \(y_i\). In this case, move the guard on \(z_i\) to \(x_i\) and consider the new matching \(M'=(M \cup \{x_iz_i\}) \backslash \{x_i y_i\}\). The invariant clearly still holds.
Since \(G\) is a graph on at least \(1+\frac{2 k c_k (k^{k-1}-1)}{k-1}\) vertices, \(V(G)\) can be partitioned into two sets \(V_1\) and \(V_2\) in a way such that at most \(k^2 < \frac{k c_k (k^{k-1}-1)}{k-1}\) guards can effectively defend the subgraph of \(G\) induced by \(V_1\) and at most \(\frac{k c_k (k^{k-1}-1)}{k-1}\) guards can effectively defend the subgraph induced by \(V_2\). This completes the proof. ◻
5 Open Problems↩︎
As shown by Klostermeyer and MacGillivray in [1], if \(G\) is a graph with independence number \(3\), then \(G\) has eviction number at most \(5\). However, it is unknown whether there exists a graph \(G\) such that \(\alpha(G)=3\) and \(e^{\infty}(G)=5\). This naturally gives rise to the following question.
Question 3. Does there exist a graph \(G\) such that \(\alpha(G)=3\) and \(e^\infty(G)=5\)?
In Proposition 5 we constructed an infinite class of connected graphs for which \(e^{\infty}/\alpha \approx4/3\). We do not know of any graph for which \(e^{\infty}/\alpha > 4/3\). The next question is more general than Question 3.
Question 4. Does there exist a graph such that \(e^{\infty}/\alpha > 4/3\)?
The upper bound on the function \(f(k)\) in Theorem 9 is much larger than \(4/3\), the largest known value of \(e^{\infty}/\alpha\), and almost certainly excessively large.
Problem 5. (Substantially) improve the bound on the function \(f(k)\) given in Theorem 9.
A cograph (or complement reducible graph) is a graph that can be generated from the trivial graph \(K_1\) by complementation and disjoint union. These graphs are also known under various characterizations, among which are the following.
A cograph is a graph that does not contain \(P_4\) as an induced subgraph.
A cograph is a graph that can be generated from the following operations:
\(K_1\) is a cograph.
If \(G_1\) and \(G_2\) are cographs, then so is \(G_1 + G_2\).
If \(G_1\) and \(G_2\) are cographs, then so is \(G_1 \vee G_2\).
Virgile [12] showed that EVICTION ETERNAL DOMINATING SET is EXPTIME-complete and that the eviction number of cographs can be computed in polynomial time. Clearly, the same holds for the graphs listed in Proposition 7.
Problem 6. Find further classes of graphs for which the eviction number can be computed in polynomial time.
Acknowledgement We acknowledge the support of the Natural Sciences and Engineering Research Council of Canada (NSERC), PIN 04459, 253271.
Cette recherche a été financée par le Conseil de recherches en sciences naturelles et en génie du Canada (CRSNG), PIN 04459, 253271.
References↩︎
Funded by a Discovery Grant from the Natural Sciences and Engineering Research Council of Canada, RGPIN-04459-2017, RGPIN-03930-2020.↩︎
This paper is based on work that appears in the doctoral dissertation”Mobile Guards’ Strategies for Graph Surveillance and Protection”by Virgélot Virgile, University of Victoria, 2024.↩︎