Gary MacGillivray, C. M. Mynhardt, Virgelot Virgile ´ ∗

Department of Mathematics and Statistics, University of Victoria, Victoria BC, Canada

gmacgill@uvic.ca, kieka@uvic.ca, virgilev@uvic.ca

We study the relationship between the eternal domination number of a graph and its clique covering number using both large-scale computation and analytic methods. In doing so, we answer two open questions of Klostermeyer and Mynhardt. We show that the smallest graph having its eternal domination number less than its clique covering number has 10 vertices. We determine the complete set of 10-vertex and 11-vertex graphs having eternal domination numbers less than their clique covering numbers. We show that the smallest triangle-free graph with this property has order 13, as does the smallest circulant graph. We describe a method to generate an infinite family of triangle-free graphs and an infinite family of circulant graphs with eternal domination numbers less than their clique covering numbers. We also consider planar graphs and cubic graphs. Finally, we show that for any integer k ≥ 2 there exist infinitely many graphs having domination number and eternal domination number equal to k containing dominating sets which are not eternal dominating sets.

Keywords: dominating sets, eternal dominating sets, independent sets, clique covering, graph protection

Mathematics Subject Classification: 05C69

DOI: 10.5614/ejgta.2022.10.2.19

1. Introduction

The eternal domination game, played on graphs, was introduced by Burger, Cockayne, Grund- ¨ lingh, Mynhardt, Van Vuuren and Winterbach [5]. The game is played between two players that

Received: 23 February 2022, Revised: 26 September 2022, Accepted: 2 October 2022.

^∗ corresponding author

alternate turns: a defender who controls a set of guards, and an attacker. To start the game, the defender chooses a dominating set D⁰ ⊆ V such that |D0| = k on which to place the guards (at most one guard on each vertex). At each time t = 1, 2, 3, . . . the attacker selects a vertex v on which there is no guard; we say the attacker attacks v. The defender responds by moving a guard on a neighbour of v to v; we say the defender defends v. The guards (or the defender) win if they are able to respond to the sequence of attacks, that is, if they can maintain a dominating set throughout the game; otherwise, the attacker wins. In other words, the attacker wins if at some time t there is no guard in the neighbourhood of some vertex. The eternal domination number of a graph G, denoted by γ ^∞(G), is the minimum number of guards necessary to respond to any sequence of attacks on G. For a survey on the eternal domination game and its variants, see [17, 18].

For graphs belonging to certain families, the eternal domination number is closely related to another well-studied parameter: the clique covering number. The clique covering number of a graph G, denoted by θ(G), is the minimum cardinality of a clique covering of G, that is, a partition {V1, V2, . . . , Vk} of V (G) such that each Vⁱ induces a clique. Observe that, as stated in [5], if we consider a minimum clique covering of G, place a guard in each clique of the covering and play the game independently in each clique, each guard is able to respond to any sequence of attacks on its respective clique. This strategy shows that the clique covering number of a graph is an upper bound on its eternal domination number. In fact, γ ^∞(G) = θ(G) if G is a perfect graph [5], an outerplanar graph [2], or a graph with θ(G) ≤ 3 [5]; a complete characterization of the graphs G with γ ^∞(G) = θ(G) is yet to be found. Goddard, Hedetniemi and Hedetniemi [10] showed that there exist graphs with γ ^∞ < θ; they gave an 11-vertex graph as example: the complement of the Grotzsch graph. Klostermeyer and Mynhardt [17] asked whether that ¨ 11-vertex graph is the smallest graph, in terms of the number of vertices, with this property. They further asked whether there exist graphs with γ ^∞ < θ in some particular graph classes, for example planar graphs.

This paper is organised as follows. In Sections 2 and 3, we review the necessary background. In Section 4, we describe a large-scale computation that shows, in Section 5.1, that the smallest graph with eternal domination number less than its clique covering number has 10 vertices and further determines the complete set of 10-vertex and 11-vertex graphs having eternal domination numbers less than their clique covering numbers. The computational results are supported by an analytic proof. In Section 5.2, we restrict our attention to triangle-free graphs, circulant graphs, planar graphs and cubic graphs. Using computation, we found that the smallest triangle-free graph with eternal domination number less than its clique covering number has 13 vertices and that the smallest circulant graph with eternal domination number less than its clique covering number has 13 vertices. We also consider a question (Question 5.1) of Klostermeyer and Mynhardt regarding triangle-free graphs. We verify that the smallest triangle-free graph with the described properties in Question 5.1, if it exists, has at least 15 vertices. Our computations also show that all planar graphs on fewer than 12 vertices, all 3-connected planar graphs on fewer than 14 vertices and all cubic graphs on fewer than 18 vertices have eternal domination numbers equal to their clique covering numbers. Finally, in Section 5.3, we consider another question (Question 5.3) and a conjecture (Conjecture 5.1) of Klostermeyer and Mynhardt. We show that the answer to Question 5.3 is no and verify Conjecture 5.1 for all graphs up to order 11.

2. Definitions

The domination number of a graph G, denoted by \(\gamma(G)\), is the minimum cardinality of a dominating set of G, that is, a set \(D \subseteq V(G)\) such that any vertex \(v \in V(G) \setminus D\) has a neighbour in D. This means that, in the eternal domination game, the guards must always be located on the vertices of a dominating set of G in order to defend a sequence of attack on G. A dominating set from which the guards can defend any sequence of attacks is known as an eternal dominating set.

The independence number of G, denoted by \(\alpha(G)\), is the maximum cardinality of an independent set of G, that is, a set \(S \subseteq V(G)\) such that for any \(u,v \in S\), \(uv \notin E(G)\). The clique number of G, denoted by \(\omega(G)\), is the maximum cardinality of a clique of G, where a clique is the complement of an independent set. This implies that \(\alpha(G) = \omega(\overline{G})\) for any graph G and its complement \(\overline{G}\).

The chromatic number of G, denoted by \(\chi(G)\), is the minimum number of colours required to colour the vertices of G so that no two adjacent vertices have the same colour. Observe that such a colouring with k colours is obtained by partitionning V(G) into \(\{V_1, V_2, \ldots, V_k\}\) where each \(V_i\) induces an independent set. For this reason, the clique covering number of a graph is equal to the chromatic number of its complement. When the graph G is clear from context, we use \(n, \alpha, \gamma^{\infty}, \theta\) to denote respectively |V(G)|, \(\alpha(G)\), \(\gamma^{\infty}(G)\), \(\theta(G)\).

A graph G is said to be vertex critical with respect to \(\theta\) if \(\theta(G - \{v\}) = \theta(G) - 1\) for any vertex \(v \in V(G)\). A graph G is said to be edge critical with respect to \(\theta\) if \(\theta(G + \{uv\}) = \theta(G) - 1\) for any edge \(uv \notin E(G)\), where \(G + \{uv\}\) is the graph obtained from G by adding the missing edge uv. Since we only consider criticality with respect to \(\theta\), we simply refer to G being vertex or edge critical without explicitly referring to \(\theta\). We say that a graph G is critical if G is vertex critical and edge critical.

The circulant graph \(C_n[k_1,k_2,\ldots,k_l]\), where \(\{k_1,k_2,\ldots,k_l\}\subseteq\mathbb{Z}^+\) and \(1\leq k_1< k_2<\cdots< k_l\leq \lfloor\frac{n}{2}\rfloor\), is the graph with vertex set \(\{v_0,v_1,v_2,\ldots,v_{n-1}\}\) such that two vertices \(v_i\) and \(v_j\) are adjacent if and only if \(i-j\equiv \pm k_p\pmod{n}\) for some \(p\in\{1,2,\ldots,l\}\). A perfect graph is a graph such that the chromatic number of any of its induced subgraphs is equal to the clique number of that subgraph.

The bow tie product of a graph G with a graph H, denoted by \(G \bowtie H\), is the graph with vertex set \(\{(v_i,v_j):v_i\in V(G),v_j\in V(H)\}\), where two vertices \((v_i,v_j)\) and \((v_i',v_j')\) are adjacent if and only if one of the following conditions holds: \(v_iv_i'\in E(G)\) and \(v_j=v_j'\), or \(v_iv_i'\in E(G)\) and \(v_jv_j'\in E(H)\) (see Figure 1). As shown in Figure 1, \(G\bowtie H\ncong H\bowtie G\) in general.

Figure 1: Bow tie product of two graphs.

We refer to a graph G as being a smallest graph having some property P if no graph H on fewer than |V (G)| vertices has property P.

3. Preliminary results

It is straightforward to see that the eternal domination number of a graph is the sum of the eternal domination number of its components; therefore, we restrict our attention to connected graphs.

We begin with the following observation that we may obtain upper and lower bounds on γ ^∞(G) by considering the problem on the induced and spanning subgraphs of G.

Fact 3.1. Let G be a graph and let H be a subgraph of G.

• (a) [15] If H is an induced subgraph of G, then γ ^∞(G) ≥ γ ^∞(H).
• (b) [2] If H is a spanning subgraph of G, then γ ^∞(G) ≤ γ ^∞(H).

The reader can easily check that γ ^∞(Kn) = 1 and γ ^∞(Kn) = n. Hence, by considering a minimum clique covering of G and playing the game independently on each clique we obtain an upper bound on γ ^∞(G). Likewise, if we consider a maximum independent set S of G and play the game on the subgraph induced by S, we obtain a lower bound on γ ^∞(G). In consequence, we have the following fact of Burger et al.

Fact 3.2 ([5]). For any graph \[G\], \(\alpha(G) \leq \gamma^{\infty}(G) \leq \theta(G)\).

The Weak Perfect Graph Theorem [19, 20] states that the complement of a perfect graph is perfect. As a direct consequence we have the following corollary.

Corollary 3.1 ([5]). For any perfect graph \[G\], \(\alpha(G) = \gamma^{\infty}(G) = \theta(G)\).

The inequalities in Fact 3.2 can both be strict. Observe that the 5-cycle is a graph with α = 2 < γ^∞ = 3 and is the smallest such graph. As for the second inequality, the first proof of the existence of a graph with γ ^∞ < θ is due to Goddard, Hedetniemi and Hedetniemi [10] and follows from Theorem 3.1 and its generalisation, Theorem 3.2, which shows that the eternal domination number of a graph is bounded above by a function of the independence number of the graph.

Theorem 3.1 ([10]). If G is a graph such that \[\alpha(G) = 2\], then \(\gamma^{\infty}(G) \leq 3\).

Theorem 3.2 ([14]). For any graph \[G\], \(\gamma^{\infty}(G) \leq {\binom{\alpha(G)+1}{2}}\).

It is known that for any integer k ≥ 2 there exists a triangle-free graph G with chromatic number k. The first known construction of a family containing such graphs with arbitrarily large chromatic numbers is due to Blanche Descartes [7, 8]. Mycielski [22] described the construction of a family F = {M2, M3, M4, . . .} of triangle-free graphs starting with M² = K2, where, for each k ≥ 3, the graph M^k is obtained from the graph Mk−¹ and has chromatic number k (see M⁴ in Figure 2a).

Figure 2: The Grötzsch graph (a) and its complement (b).

Corollary 3.2 ([10]). For any integer \(k \geq 4\), \(\gamma^{\infty}(\overline{M_k}) < \theta(\overline{M_k})\).

Our primary purpose in this paper is to study the relationship between the eternal domination number and the clique covering number for some specific graphs; however, Theorem 3.2 implies a nice result on the problem regarding general random graphs that is worth mentioning.

Theorem 3.3 ([1], Theorem 3.1). For almost all graphs G, \(\alpha(G) \leq (2 + o(1)) \log_2 n\) and \(\theta(G) \geq (1 + o(1)) \frac{n}{2 \log_2 n}\).

Corollary 3.3. For almost all graphs G, \(\gamma^{\infty}(G) < \theta(G)\).

Proof. We know from Theorem 3.3 that \(\alpha(G) \leq (2+o(1))\log_2 n\) for almost all graphs G. Together with Theorem 3.2, this implies that \(\gamma^\infty(G) \leq (2+o(1))(\log_2 n)^2\) for almost all graphs G. Since \(\lim_{n\to\infty} \frac{2(\log_2 n)^2}{n/(2\log_2 n)} = 0\), we conclude that \(\gamma^\infty(G) < \theta(G)\) for almost all graphs G.

Theorem 3.4 ([6]). The Grötzsch graph (Figure 2a) is the unique smallest triangle-free graph with chromatic number at least 4.

Corollary 3.4. The complement of the Grötzsch graph is the unique smallest graph with independence number 2 and clique covering number at least 4.

Klostermeyer and Mynhardt [17, 18] posed the following questions.

Question 3.1 ([17]). Is the complement of the Grötzsch graph, a graph of order 11, the smallest graph with eternal domination number less than its clique covering number?

Question 3.2 ([18]). Let G be a graph with \(\gamma(G) = \gamma^{\infty}(G)\). Is any minimum dominating set of G an eternal dominating set of G?

We answer Question 3.1 in Section 5.1 by finding two graphs of order 10 with this property. We also show that the answer to Question 3.2 is no by constructing an infinite family of counterexamples.

4. Computational methods

Consider the following decision problem.

ETERNAL DOMINATION

INSTANCE: A graph G and an integer k > 0.

QUESTION: Is γ ^∞(G) ≤ k?

Although the precise complexity of ETERNAL DOMINATION is not known for general graphs, Klostermeyer and MacGillivray [13] showed that the problem can be solved in time exponential in n. Their algorithm is described for a variant of the eternal domination game. Algorithm 1 is adapted to the version of the game considered in this paper. Klostermeyer also studied the complexity of the problem under narrow assumptions on the sequence of attacks [12].

The precise complexity of ETERNAL DOMINATION is known for graphs belonging to certain graph classes, for example perfect graphs. We know from Corollary 3.1 that the eternal domination number of a perfect graph is equal to its independence number and hence its clique covering number. It is well known [11] that the independence number of a perfect graph can be found in polynomial time in n. As a result, ETERNAL DOMINATION is in P for perfect graphs.

Algorithm 1 ([13]). Determine whether γ ^∞(G) ≤ k.

Given G, construct an arc-coloured digraph D as follows.

• 1. The vertex set of D is the set of k-vertex dominating sets of G. The set of colours is V (G). There is an arc from X to Y of colour v when Y − X = {v}, and v is adjacent in G to the unique vertex w ∈ X − Y .
• 2. Delete any vertex X which is not the origin of an arc coloured x for some x ∈ V (G)\X.
• 3. Repeat Step 2 until no further vertices can be deleted.

If D is the null graph, then γ ^∞(G) > k; otherwise, γ ^∞(G) ≤ k.

In the following section, we report on a large-scale computation performed on a PowerEdge R7425 server equipped with two AMD EPYC processors and totalling 64 threaded CPU cores for the purposes of verifying some of the propositions in the paper. The computations were done in Python using NetworkX and Algorithm 1 along with a few basic graph algorithms.

In our search, we often needed to generate the set of all graphs belonging to some particular class; to this end, we used NAUTY [21] (version 2.7001) and PLANTRI [4, 3] (version 5.2). On one hand, using NAUTY, we were able to generate the set of all graphs, the set of all triangle-free graphs, and the set of all cubic graphs of order n for some given values of n. On the other hand, using PLANTRI, we were able to generate the set of all planar graphs of order n for some given values of n.

Since we studied the relationship between the eternal domination number and other graph parameters such as the domination number, the independence number and the clique covering number, we also found the value of each of these parameters for each graph in our computation.

We computed the independence number of each graph by computing the clique number of its complement using the built-in functions complement() and graph_clique_number() from the Python package NetworkX. As for the clique covering number, we computed this value using three different approaches. For general graphs, we started by enumerating the set of maximal cliques of the graph using the built-in function find_cliques() from NetworkX. Using a naive method and an integer programming method, we found the size of the smallest subset of the set of maximal cliques which covers all the vertices of the graph. To solve the integer programs, we used the Python packages PuLP and MIP and they both agreed on the results. Our naive method is on average faster than the integer programming method on the set of graphs of up to order 11. When it is known in advance that the graph is triangle-free, we first found the size of a maximum matching in the graph using the function max_weight_matching() from NetworkX and then substracted this number from the order of the graph. As for the domination number of the graph, we found this value by first generating the k-vertex subsets of the n-vertex set. Then, using the built-in function is_dominating_set from NetworkX, we checked whether the graph had a dominating set of that size.

Now, to find the the eternal domination number of the graph, we first compared its independence number to its clique covering number using the algorithms described above. If these parameters are equal, then they are also equal to the eternal domination number. Otherwise, we computed the eternal domination number using Algorithm 1. The largest single computation took approximately 218 CPU days before the results (Table 2) were found. The class of graphs on which our computations were the slowest is the set of maximal triangle-free graphs with independence numbers less than their clique covering numbers.

5. Main results

5.1. General graphs

In this section, we show that the graphs G¹ and G² depicted in Figure 3 are the smallest graphs having their eternal domination numbers less than their clique covering numbers. Observe that G² is obtained from G¹ by adding the edge (67).

Figure 3: Smallest graphs with γ^∞ < θ.

We first show that these graphs have eternal domination numbers less than their clique covering numbers. To this end, we begin with the following facts; the proofs are easy and left to the reader.

Figure 4: Complements of the graphs in Figure 3.

Fact 5.1. For the graphs G1, G2, G¹ and G² depicted in Figures 3 and 4,

(a) \[\alpha(G_1) = \alpha(G_2) = \omega(\overline{G_1}) = \omega(\overline{G_2}) = 3.\]

(b) \[\theta(G_1) = \theta(G_2) = \chi(\overline{G_1}) = \chi(\overline{G_2}) = 4.\]

Fact 5.2. The graph G¹ contains exactly six triangles, namely {2, 3, 4}, {5, 6, 7}, {0, 2, 8}, {0, 1, 7}, {1, 3, 9} and {6, 8, 9}, any two of which share at most one vertex.

Fact 5.3. The subgraph induced by the vertices in the open neighbourhood of each vertex of G¹ is isomorphic to either 2K² or to K¹ ∪ K2.

The following result can be verified by computer, but we include a proof as well.

Proposition 5.1. For the graphs G¹ and G² depicted in Figure 3, γ ^∞(G1) = γ ^∞(G2) < θ(G1) = θ(G2).

Proof. Since G¹ is a spanning subgraph of G2, it suffices to show that γ ^∞(G1) = 3. Fact 3.1 will then imply that γ ^∞(G2) = 3. We do this by contradiction and assume that γ ^∞(G1) ≥ 4. We may also assume without loss of generality that three guards are initially located on the vertices of an independent set of G1. This is because the attacker may sequentially attack all the vertices of a maximum independent set of G¹ and force a guard to be located on each of them. Let k be the smallest integer such that there exists a sequence of attacks of length k that the three guards cannot defend. Suppose the guards respond optimally to that sequence of attacks. At time t = k − 1, they will be located on the vertices b, c and d, none of which is adjacent to vertex a (see Figure 5 where a thick black edge corresponds to an edge in G¹ and a thin blue edge corresponds to an edge in G1).

Figure 5: Configuration of the guards at time t = k − 1.

Following Fact 5.3, we may assume that vertex c is not adjacent to vertex d and vertex b is adjacent to both of c and d. So, we colour the edge cd blue and the edges bc and bd black (see Figure 6).

Figure 6: Configuration of the guards at time t = k − 1.

Note that in the previous time (t = k − 2), the guards dominated all the vertices of G, in particular vertex a was dominated. We now consider two cases depending on the location of the guards at time t = k − 2.

• Case 1, In the previous turn, a guard moved from a vertex e to vertex c (see Figure 7b). In this case, e is adjacent to a because a was dominated at time t = k −2 but is undominated at time t = k − 1, and b has a neighbour f which is non-adjacent to all of c, d and e (otherwise the guards would still be on a dominating set if the guard on b moved to c instead; see Figure 7c). This contradicts Fact 5.2 since the thin blue triangles {a, c, d} and {f, c, d} share two vertices (c and d; see Figure 7c).

Figure 7: Configuration of the guards in Case 1 of the proof of Proposition 5.1.

• Case 2. In the previous turn, a guard moved from vertex e to vertex b (see Figure 8b). In this case, c has a neighbour f which is non-adjacent to b, d and e (otherwise the guards would still be on a dominating set if the guard on c moved to b instead). For the same reason, d has a neighbour g which is not adjacent to b, c and e, as shown in Figure 8c. Following Fact 5.2, f must be adjacent to g, otherwise {f, b, g} and {f, e, g} would be two thin blue triangles sharing two vertices. By the same fact, a must be adjacent to f as {a, c, d} and {a, f, d} would share two vertices otherwise. For a similar reason, a must be adjacent to g as {a, c, g} and {a, c, d} would be two thin blue triangles sharing two vertices otherwise (see Figure 8d).

Now, the edges ce and de cannot be both thin blue, otherwise the thin blue triangles {a, c, d} and {e, c, d} would share two vertices. We assume without loss of generality that the edge ce is black and we consider the two choices for the colour of the edge de.

Figure 8: Configuration of the guards in Case 2 of the proof of Proposition 5.1.

So, we obtain two blue/black colourings of the edges of the complete graph on 7 vertices. One of the thin blue subgraphs obtained (Figure 9) must be an induced subgraph of G1.

Figure 9: Induced subgraphs of G1.

The reader can check that G¹ does not contain any of those graphs as an induced subgraph. Hence, we obtain a contradiction and conclude that γ ^∞(G1) = 3.

In the remaining part of this section, we verify that any graph with fewer than 10 vertices has eternal domination number equal to its clique covering number.

Proposition 5.2. For any graph G of order 9 or less, γ ^∞(G) = θ(G).

Proposition 5.2 was verified by computer; the search can be described as follows. Suppose G is a smallest graph such that γ ^∞(G) < θ(G) with the maximum number of edges. Fact 3.2 implies that α(G) < θ(G); moreover, by the choice of G and Fact 3.1, deleting a vertex from the graph or adding a missing edge to the graph decreases its clique covering number by 1. Consequently, G is a critical graph. Table 1 shows the number of critical graphs of order 9 or less and each of these graphs is either drawn in Figures 10 or 11, or listed in Graph6 format in Table 8 in the appendix. Using the computational methods described in Section 4 we checked that each of these graphs has eternal domination number equal to its clique covering number.

Using a similar technique, without considering only critical graphs, we found the complete set of 10-vertex and 11-vertex graphs with γ ^∞ < θ. Those graphs are listed in Table 9 in the appendix in Graph6 format.

Table 1: Number of critical graphs on n vertices with γ^∞ < θ.

The graph C⁵ is the only critical graph of order 5 with α < θ. We display the critical graphs of order 7 and 8 in Figures 10 and 11, and list the critical graphs of order 9 with α < θ in Graph6 format in the appendix (Table 8).

Figure 10: Critical graphs of order 7 with α < θ.

Figure 11: Critical graphs of order 8 with α < θ.

5.2. Graph Classes

In this section, we focus on different classes of graphs, starting with triangle-free graphs in Sections 5.2.1 and 5.2.2, before moving on to circulant graphs in Section 5.2.3 and planar graphs in Section 5.2.4. We briefly mention claw-free graphs in Section 5.2.5 and cubic graphs in Section 5.2.6.

5.2.1. Triangle-free graphs

Erdos, Kleitman and Rothschild [9] showed that almost all triangle-free graphs are bipartite, ˝ therefore almost all triangle-free graphs are perfect and satisfy γ ^∞ = θ. However, Goddard,

Hedetniemi and Hedetniemi [10] showed that there exist triangle-free graphs with γ ^∞ < θ. They gave the circulant graphs C18[1, 3, 8] and C21[1, 3, 8], which they found using computer assistance, as examples. Using Algorithm 1, we checked that any triangle-free graph of order 12 or less has eternal domination number equal to its clique covering number. We found 13 triangle-free graphs of order 13 with γ ^∞ < θ (see Table 10). Previously the smallest known triangle-free graph with this property has 17 vertices and is a subgraph of the circulant graph C18[1, 3, 8]. The following corollary describes a way to generate an infinite family of triangle-free graphs with γ ^∞ < θ.

Fact 5.4. Let G be a triangle-free graph. Then G ▷◁ K² is triangle-free.

Corollary 5.1. Let G be a triangle-free graph such that γ ^∞(G) < θ(G) = ⌈ n 2 ⌉. Then, γ ^∞(G ▷◁ K2) < θ(G ▷◁ K2).

Proof. Let G be a triangle-free graph such that γ ^∞(G) < θ(G) = ⌈ n 2 ⌉. Fact 5.4 implies that G ▷◁ K² is triangle-free; as a result, θ(G ▷◁ K2) ≥ n. Observe that the vertices of G ▷◁ K² can be partitionned into two subsets, each of which induces a subgraph isomorphic to G. This means that γ ^∞(G ▷◁ K2) ≤ 2γ ^∞(G) < 2⌈ n 2 ⌉; consequently, γ ^∞(G ▷◁ K2) ≤ n − 1.

Klostermeyer and Mynhardt [16] posed the following question.

Question 5.1 ([16]). Does there exist a triangle-free graph G such that α(G) = γ ^∞(G) < θ(G)?

Note that the 13 triangle-free graphs on 13 vertices with γ ^∞ < θ we found also satisfy α < γ ^∞ < θ. In Proposition 5.3, we describe a property of a smallest such a graph (if it exists), then we show by using computer assistance that no graph of order 14 or less satisfies this property.

Proposition 5.3. Suppose there exist triangle-free graphs with α = γ ^∞ < θ and let G be such a graph with minimum order. Let X be a maximum independent set of G and let Y = V (G) − X. Then |X| = |Y | − 1.

Proof. It is clear that |X| ≥ |Y | − 1, otherwise, by Fact 3.1, α(G − {v}) = γ ^∞(G − {v}) < θ(G − {v}) for any v ∈ Y , and G − {v} would be a smaller triangle-free graph with α = γ ^∞ < θ. So, it remains to show that |X| ≤ |Y | − 1. Suppose this is false, in other words |X| ≥ |Y |. Let G′ be the spanning bipartite subgraph of G obtained by deleting all edges having both endpoints in Y . Observe that the graph G′ does not contain a matching that covers all of the vertices in Y , otherwise, G would contain a matching that matches each vertex in Y to a vertex in X, and this would imply that α(G) = θ(G) (contradiction). Consequently, by Hall's matching condition, Y contains a subset S such that |NG′(S)| < |S|. Now, consider the subgraph H of G induced by S ∪ NG′(S). Since there is no edge between a vertex in H and a vertex in X − V (H), we have α(H) = |NG′(S)|, otherwise G contains an independent set of size at least |X| + 1. Moreover, since γ ^∞(G) = |X| we must have γ ^∞(H) = |NG′(S)|: this is true because the attacker may force the |X| guards to be located in X and from there only attacks the vertices in H. In this case, only the |NG′(S)| guards are able to respond to that sequence of attacks on H. Hence, H would be a smaller triangle-free graph with α = γ ^∞ < θ.

Figure 12: Cases considered in the proof of Proposition 5.3.

Using the property stated in Proposition 5.3, to find the smallest triangle-free graph G with \(\alpha = \gamma^{\infty} < \theta\) we only need to check the triangle-free graphs of order 2k+1 with \(\alpha = k\) and \(\theta = k+1\). Again, using NAUTY, we generated the set of triangle-free graphs of odd orders on fewer than 14 vertices; then, we computed the independence number and the clique covering number of each of these graphs using the algorithms described above. If \(\alpha = \frac{n-1}{2}\) and \(\theta = \frac{n+1}{2}\), then we computed the eternal domination number of the graph. We performed the computation listed in Table 2 on a cluster which required approximately 218 CPU days.

Observation 5.1. There are no triangle-free graphs on \(n \leq 14\) vertices with \(\alpha = \gamma^{\infty} < \theta\).

Table 2: Number of connected triangle-free graphs on n vertices with \(\alpha = \lfloor \frac{n}{2} \rfloor\) and \(\theta = \lceil \frac{n}{2} \rceil\).

5.2.2. Maximal triangle-free graphs

A graph G is said to be maximal triangle-free if G is triangle-free and the insertion of any missing edge in G creates a triangle. The maximal triangle-free graphs are considered to be an interesting family of graphs since several problems on triangle-free graphs can be studied by restricting attention to maximal triangle-free graphs. Observe that if G is a triangle-free graph with \(\lfloor \frac{n}{2} \rfloor = \alpha = \gamma^{\infty} < \theta = \lceil \frac{n}{2} \rceil\), then G is a subgraph of a maximal triangle-free graph with \(\gamma^{\infty} < \theta = \lceil \frac{n}{2} \rceil\). This follows since the clique covering number of a triangle-free graph G is at least \(\lceil \frac{n}{2} \rceil\) and adding any missing edge to G that does not create a triangle increases neither its clique covering number nor its eternal domination number.

Proposition 5.4. Suppose there exist maximal triangle-free graphs with α = γ ^∞ < θ and let G be such a graph with minimum order. Let X be a maximum independent set of G and Y = V (G)−X. Then |X| = |Y | − 1.

Proof. Same proof as Proposition 5.3.

Observation 5.2. There are no maximal triangle-free graphs on n ≤ 16 vertices with α = γ ^∞ < θ.

Observation 5.2 was verified using a similar computer search as in Observation 5.1.

Table 3: Number of maximal triangle-free graphs on n vertices with α = ⌊ n 2 ⌋ and θ = ⌈ n 2 ⌉.

5.2.3. Circulant graphs

Circulant graphs are another interesting family of graphs on which we study the problem. Using Algorithm 1, we found all the circulant graphs of order 20 or less with γ ^∞ < θ (see Table 4).

Table 4: List of small circulant graphs with γ^∞ < θ.

Proposition 5.5. For any integer n, \(C_n[k_1, k_2, ..., k_l] \bowtie K_2 \cong C_{2n}[2k_1, 2k_2, ..., 2k_l, 2k_1 + 1, 2k_2 + 1, ..., 2k_l + 1].\)

Proof. Let \(G = C_n[k_1, k_2, ..., k_l]\) be a circulant graph and let \(H = C_n[k_1, k_2, ..., k_l] \bowtie K_2\). Suppose \(V(G) = \{v_1, v_2, ..., v_n\}\) and \(V(K_2) = \{0, 1\}\). For each \(i \in \{1, 2, ..., n\}\), let \(u_{2i} = (v_i, 0)\) and \(u_{2i+1} = (v_i, 1)\). The definition of the bow tie product implies the following statements:

• The vertices \(u_{2i}\) and \(u_{2j}\) are adjacent in H if and only if the vertices \(v_i\) and \(v_j\) are adjacent in G; that is, if and only if \(i j \equiv \pm k \pmod{n}\) for some \(k \in \{k_1, k_2, \dots, k_p\}\). Equivalently, \(u_{2i}\) is adjacent to \(u_{2j}\) if and only if \(2i 2j \equiv \pm k \pmod{2n}\) for some \(k \in \{2k_1, 2k_2, \dots, 2k_l\}\).
• The vertices \(u_{2i+1}\) and \(u_{2j+1}\) are adjacent in H if and only if the vertices \(v_i\) and \(v_j\) are adjacent in G. Therefore, \(u_{2i+1}\) is adjacent to \(u_{2j+1}\) if and only if \(2i-2j\equiv \pm k\pmod{2n}\) for some \(k\in\{2k_1,2k_2,...,2k_l\}\).
• The vertices \(u_{2i+1}\) and \(u_{2j}\) are adjacent in H if and only if the vertices \(v_i\) and \(v_j\) are adjacent in G; that is, if and only if \(i-j\equiv \pm k\pmod n\) for some \(k\in \{k_1,k_2,\ldots,k_p\}\). Equivalently, \(u_{2i+1}\) is adjacent to \(u_{2j}\) if and only if \((2i+1)-2j\equiv \pm k\pmod {2n}\) for some \(k\in \{2k_1+1,2k_2+1,\ldots,2k_l+1\}\).

Thus, for each \(i, j \in \{0, 1, 2, \dots, 2n-1\}\), the vertices \(u_i\) and \(u_j\) are adjacent if and only if \(i-j \equiv \pm k \pmod{2n}\) for some \(k \in \{2k_1, 2k_2, \dots, 2k_l, 2k_1+1, 2k_2+1, \dots, 2k_l+1\}\).

Corollary 5.2. There exist infinitely many circulant graphs with \(\gamma^{\infty} < \theta\).

Proof. This follows from Fact 5.4, Corollary 5.1 and Proposition 5.5.

5.2.4. Planar graphs

Anderson, Barrientos, Brigham, Carrington, Vitray and Yellen [2] showed that any outerplanar graph has eternal domination number equal to its clique covering number. Moreover, no planar graph where \(\gamma^{\infty} < \theta\) is known. This suggest that it might be true for general planar graphs and motivates the following question of Klostermeyer and Mynhardt.

Question 5.2 ([17]). Is it true that \(\gamma^{\infty}(G) = \theta(G)\) if G is planar?

We first describe some properties of a smallest planar graph with \(\gamma^{\infty} < \theta\), if it exists.

Proposition 5.6. Let \(\mathcal{F}\) be a family of graphs satisfying a hereditary property \(\mathcal{P}\); i.e. if \(G \in \mathcal{F}\) and G satisfies property \(\mathcal{P}\), then H satisfies property \(\mathcal{P}\) for any subgraph H of G. Suppose \(\mathcal{F}\) contains graphs G such that \(\gamma^{\infty}(G) < \theta(G)\). Then, the smallest such graph G is a 2-connected vertex critical graph.

Proof. It is clear that G is a vertex-critical graph; otherwise, by Fact 3.1, G contains a proper induced subgraph which is also in \(\mathcal{F}\) with \(\gamma^{\infty} < \theta\) (contradiction). Suppose G is not 2-connected and let v be a cut vertex of G, that is a vertex such that \(G - \{v\}\) has k components \(\{G_1, G_2, \ldots, G_k\}\) where \(k \geq 2\). By the minimality of G, \(\gamma^{\infty}(G_i) = \theta(G_i)\) for each \(i \in \{1, 2, \ldots, k\}\). Since \(\gamma^{\infty}(G) \geq \sum_{i=1}^k \gamma^{\infty}(G_i)\), \(\theta(G) \leq \sum_{i=1}^k \theta(G_i) + 1\) and \(\gamma^{\infty}(G) < \theta(G)\), we conclude that \(\gamma^{\infty}(G) = 0\)

\(\sum_{i=1}^k \gamma^\infty(G_i)\) and \(\theta(G) = \sum_{i=1}^k \theta(G_i) + 1\). This implies that there exists \(i \in \{1, 2, \dots, k\}\) such that \(\gamma^\infty(G_i) = \gamma^\infty(G_i + \{v\})\) and \(\theta(G_i + \{v\}) = \theta(G_i) + 1\). In this case, \(G_i + \{v\}\) is a smaller graph in \(\mathcal F\) with \(\gamma^\infty < \theta\), which is a contradiction.

Since planarity is a hereditary property, the smallest planar graph with \(\gamma^{\infty} < \theta\), if it exists, is a 2-connected vertex-critical graph. Observe that none of the graphs on 11 vertices or less satisfying \(\gamma^{\infty} < \theta\) we found (Table 9) are planar, hence we have the following observation.

Observation 5.3. There are no planar graphs on 11 vertices or less with \(\gamma^{\infty} < \theta\).

We also considered planar graphs of higher orders (12 and 13) in our search and we used plantri [4, 3] (version 5.2) to generate them. Due to the limitations of plantri, we only considered 3-connected planar graphs and obtained the following observation.

Observation 5.4. There are no 3-connected planar graphs on 13 vertices or less with \(\gamma^{\infty} < \theta\).

Table 5: Number of 3-connected planar graphs on n vertices.

5.2.5. Claw-free graphs

A claw-free graph is a graph that does not contain a claw as an induced subgraph. In particular, any graph with independence number 2 is claw-free. The complements of the Mycielski graphs \(M_k\) described in Section 3 have independence number 2, eternal domination number 3 and clique covering number k for \(k \geq 4\). Consequently, there are infinitely many claw-free graphs with \(\gamma^{\infty} < \theta\).

5.2.6. Cubic graphs

A cubic graph is a graph in which all vertices have degree 3. Using NAUTY along with Algorithm 1, we generated the set of cubic graphs on fewer than 18 vertices and obtained the following observation.

Observation 5.5. There are no cubic graph on \(n \leq 16\) vertices with \(\gamma^{\infty} < \theta\).

Table 6: Number of connected cubic graphs on n vertices.

5.3. Domination, eternal domination and clique covering

As we have seen above, the guards must always be located on the vertices of a dominating set in a graph G in order to defend a sequence of attacks on G. With this in mind, many researchers showed interest in characterizing graphs for which the domination number is equal to the eternal domination number. Klostermeyer and Mynhardt [18] posed the following question.

Question 5.3 ([18]). Let G be a graph with γ(G) = γ ^∞(G). Is any minimum dominating set of G an eternal dominating set of G?

The answer to Question 5.3 is no. We state this in the following proposition.

Proposition 5.7. For any integer k ≥ 2, there exists a graph G such that γ(G) = γ ^∞(G) = k having minimum dominating sets which are not eternal dominating sets.

Proof. Consider the graph G¹ in Figure 13a. It can be easily checked that γ(G1) = γ ^∞(G1) = θ(G1) = 2. Moreover, the set {u1, u4} is a dominating set of G; however, if the guards are located on the vertices u¹ and u4, then any response to an attack on the vertex u⁰ leaves either the vertex u² or the vertex u³ undominated on the next turn. Figure 13b shows a generalisation of the graph in Figure 13a where γ(G2) = γ ^∞(G2) = k. The set {u1, u4} ∪ {v0, v1, . . . , vk−3} is a dominating set of size k, but any response to an attack on vertex u⁰ leaves one of the vertices u2, u³ or w⁰ undominated on the next turn.

(a) A graph G¹ with γ(G1) = γ∞(G1) = 2 having more minimum dominating sets than eternal dominating sets.

(b) A graph G² with γ(G2) = γ∞(G2) = k having more minimum dominating sets than eternal dominating sets.

Figure 13: Two graphs having more minimum dominating sets than eternal dominating sets.

A question of Klostermeyer and MacGillivray, which was later stated as a conjecture by Klostermeyer and Mynhardt, is the following.

Conjecture 5.1 (γ − θ Conjecture [17, 18]). For any graph G, γ(G) = γ ^∞(G) ⇐⇒ γ(G) = θ(G).

Our computer search yields the following observation.

Observation 5.6. There are no counterexample to the γ − θ conjecture of order n ≤ 11.

Table 7: Number of connected graphs on n vertices with γ = α, γ = γ^∞ and γ = θ.

The computation in Table 7 was performed on a cluster which required approximately 85 CPU days. We found 56 graphs (listed in Table 9 in the appendix) with γ ^∞ < θ among which there are 55 graphs with α = γ ^∞ < θ and none with γ = γ ^∞ < θ.

Acknowledgement

All the computations in this paper were run on a PowerEdge R7425 server equipped with two AMD EPYC processors and totalling 64 threaded CPU cores. This machine was purchased using NSERC funding by Wendy Myrvold. We thank Wendy for her help with the computations.

We acknowledge the support of the Natural Sciences and Engineering Research Council of Canada (NSERC), PIN 04459, 253271.

Cette recherche a et´ e financ ´ ee par le Conseil de recherches en sciences naturelles et en g ´ enie ´ du Canada (CRSNG), PIN 04459, 253271.

References

• [1] N. Alon and J.H. Spencer, The probabilistic method. With an appendix by Paul Erdos, ˝ Wiley-Interscience Series in Discrete Mathematics and Optimization, John Wiley & Sons, (1992).
• [2] M. Anderson, C. Barrientos, R.C. Brigham, J.R. Carrington, R.P. Vitray, and J. Yellen, Maximum-demand graphs for eternal security, J. Combin. Math. Combin. Comput. 61 (2007), 111–127.

• [3] G. Brinkmann and B. D. McKay, The program plantri, Available at https://users. cecs.anu.edu.au/˜bdm/plantri/
• [4] G. Brinkmann and B.D. McKay, Fast generation of planar graphs, MATCH Commun. Math. Comput. Chem. 58 (2007), no. 2, 323–357.
• [5] A.P. Burger, E.J. Cockayne, W.R. Grundlingh, C.M. Mynhardt, J.H. van Vuuren, and W. Win- ¨ terbach, Infinite order domination in graphs, J. Combin. Math. Combin. Comput. 50 (2004), 179–194.
• [6] V. Chvatal, The minimality of the Mycielski graph, ´ Graphs and Combinatorics (Proc. Capital Conf., George Washington Univ., Washington, D.C., 1973), Lecture Notes in Math. 406 (1974), 243–246, Springer, Berlin.
• [7] B. Descartes, A three colour problem, Eureka 9 (1947), 21.
• [8] B. Descartes, Solution to advanced problem no. 4526, Amer. Math. Monthly 61 (1954), 352.
• [9] P. Erdos, D.J. Kleitman, and B.L. Rothschild, Asymptotic enumeration of ˝ Kn-free graphs, Colloquio Internazionale sulle Teorie Combinatorie (Rome, 1973), 2 (1976), 19–27.
• [10] W. Goddard, S.M. Hedetniemi, and S.T. Hedetniemi, Eternal security in graphs, J. Combin. Math. Combin. Comput. 52 (2005), 169–180.
• [11] M. Grotschel, L. Lov ¨ asz, and A. Schrijver, Geometric algorithms and combinatorial opti- ´ mization, Springer-Verlag, (1988).
• [12] W.F. Klostermeyer, Complexity of eternal security, J. Combin. Math. Combin. Comput. 61 (2007), 135–140.
• [13] W.F. Klostermeyer, M. Lawrence, and G. MacGillivray, Dynamic dominating sets: the eviction model for eternal domination, J. Combin. Math. Combin. Comput. 97 (2016), 247–269.
• [14] W.F. Klostermeyer and G. MacGillivray, Eternal security in graphs of fixed independence number, J. Combin. Math. Combin. Comput. 63 (2007), 97–101.
• [15] W.F. Klostermeyer and G. MacGillivray, Eternal dominating sets in graphs, J. Combin. Math. Combin. Comput. 68 (2009), 97–111.
• [16] W.F. Klostermeyer and C.M. Mynhardt, Domination, eternal domination and clique covering, Discuss. Math. Graph Theory 35(2) (2015), 283–300.
• [17] W.F. Klostermeyer and C.M. Mynhardt, Protecting a graph with mobile guards, Appl. Anal. Discrete Math. 10(1) (2016), 1–29.
• [18] W.F. Klostermeyer and C.M. Mynhardt, Eternal and secure domination in graphs, Topics in domination in graphs, Dev. Math. 64 (2020), 445–478, Springer, Cham.

• [19] L. Lovasz, A characterization of perfect graphs, ´ J. Combin. Theory Ser. B 13 (1972), 95–98.
• [20] L. Lovasz, Normal hypergraphs and the perfect graph conjecture, ´ Discrete Math. 2(3) (1972), 253–267.
• [21] B.D. McKay and A. Piperno, Practical graph isomorphism, II, J. Symbolic Comput. 60 (2014), 94–112.
• [22] J. Mycielski, Sur le coloriage des graphes, Colloq. Math. 3 (1955), 161–162.

Appendix

All the graphs in this appendix are listed in Graph6 format.

Table 8: List of critical graphs with α < θ.

Table 9: List of connected graphs with γ^∞ < θ.

Table 10: List of triangle-free graphs with γ^∞ < θ.

Table 11: List of maximal triangle-free graphs with γ^∞ < θ.