ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 20 (2021) 129–142
https://doi.org/10.26493/1855-3974.2227.e1a
(Also available at http://amc-journal.eu)
The enclaveless competition game
Michael A. Henning *
Department of Mathematics and Applied Mathematics, University of Johannesburg,
Auckland Park, 2006 South Africa
Douglas F. Rall
Professor Emeritus of Mathematics
Furman University, Greenville, SC, USA
Received 24 January 2020, accepted 11 November 2020, published online 19 August 2021
Abstract
For a subset S of vertices in a graph G, a vertex v ∈ S is an enclave of S if v and
all of its neighbors are in S, where a neighbor of v is a vertex adjacent to v. A set S is
enclaveless if it does not contain any enclaves. The enclaveless number Ψ(G) of G is the
maximum cardinality of an enclaveless set in G. As first observed in 1997 by Slater, if G is
a graph with n vertices, then γ(G)+Ψ(G) = n where γ(G) is the well-studied domination
number of G. In this paper, we continue the study of the competition-enclaveless game
introduced in 2001 by Philips and Slater and defined as follows. Two players take turns in
constructing a maximal enclaveless set S, where one player, Maximizer, tries to maximize
|S| and one player, Minimizer, tries to minimize |S|. The competition-enclaveless game
number Ψ+g (G) of G is the number of vertices played when Maximizer starts the game and
both players play optimally. We study among other problems the conjecture that if G is
an isolate-free graph of order n, then Ψ+g (G) ≥ 12n. We prove this conjecture for regular
graphs and for claw-free graphs.
Keywords: Competition-enclaveless game, domination game.
Math. Subj. Class. (2020): 05C65, 05C69
1 Introduction
In 2010 Brešar, Klavžar, and Rall [2] published the seminal paper on the domination game
which belongs to the growing family of competitive optimization graph games. Domi-
nation games played on graphs are now very well studied in the literature. Indeed, the
*Research supported in part by the University of Johannesburg.
E-mail addresses: mahenning@uj.ac.za (Michael A. Henning), doug.rall@furman.edu (Douglas F. Rall)
cb This work is licensed under https://creativecommons.org/licenses/by/4.0/
130 Ars Math. Contemp. 20 (2021) 129–142
subsequent rapid growth by the scientific community of research on domination games
played on graphs resulted in several dozen papers to date on the domination-type games
(see, for example, [3, 4, 10, 11, 12, 14, 17]). A recent book entitled “Domination games
played on graphs” by Brešar, Henning, Klavžar, and Rall [1] presents the state of the art
results to date, and shows that the area is rich for further research. In this paper, we con-
tinue the study of domination games played on graphs, and investigate in more depth the
competition-enclaveless game birthed by Philips and Slater [15, 16].
A neighbor of a vertex v in G is a vertex that is adjacent to v. A vertex dominates itself
and its neighbors. A dominating set of a graph G is a set S of vertices of G such that every
vertex in G is dominated by a vertex in S. The domination number of G, denoted γ(G),
is the minimum cardinality of a dominating set in G, while the upper domination number
of G, denoted Γ(G), is the maximum cardinality of a minimal dominating set in G. A
minimal dominating set of cardinality Γ(G) we call a Γ-set of G.
The open neighborhood of a vertex v in G is the set of neighbors of v, denoted NG(v).
Thus, NG(v) = {u ∈ V | uv ∈ E(G)}. The closed neighborhood of v is the set NG[v] =
{v} ∪NG(v). If the graph G is clear from context, we simply write N(v) and N [v] rather
than NG(v) and NG[v], respectively.
As defined by Alan Goldman and introduced by Slater in [19], for a subset S of vertices
in a graph G, a vertex v ∈ S is an enclave of S if it and all of its neighbors are also in S;
that is, if N [v] ⊆ S. A set S is enclaveless if it does not contain any enclaves. We note that
a set S is a dominating set of a graph G if and only if the set V (G) \ S is enclaveless. The
enclaveless number of G, denoted Ψ(G), is the maximum cardinality of an enclaveless set
inG, and the lower enclaveless number ofG, denoted by ψ(G), is the minimum cardinality
of a maximal enclaveless set. The domination and enclaveless numbers of a graph G are
related by the following equations.
Observation 1.1. If G is a graph of order n, then γ(G) + Ψ(G) = n = Γ(G) + ψ(G).
The domination game on a graph G consists of two players, Dominator and Staller,
who take turns choosing a vertex from G. Each vertex chosen must dominate at least one
vertex not dominated by the vertices previously chosen. Upon completion of the game, the
set of chosen (played) vertices is a dominating set in G. The goal of Dominator is to end
the game with a minimum number of vertices chosen, while Staller has the opposite goal
and wishes to end the game with as many vertices chosen as possible.
The Dominator-start domination game and the Staller-start domination game is the
domination game when Dominator and Staller, respectively, choose the first vertex. We
refer to these simply as the D-game and S-game, respectively. The game domination num-
ber, γg(G), of G is the number of moves in a D-game when both players play optimal
strategies consistent with their goals. The Staller-start game domination number, γ′g(G),
of G is defined analogously for the S-game.
Philips and Slater [15, 16] introduced what they called the competition-enclaveless
game. The game is played by two players, Maximizer and Minimizer, on some graph
G. They take turns in constructing a maximal enclaveless set S of G. That is, in each turn
a player plays a vertex v that is not in the set S of the vertices already chosen and such that
S ∪ {v} does not contain an enclave, until there is no such vertex. We call such a vertex a
playable vertex. The goal of Maximizer is to make the final set S as large as possible and
for Minimizer to make the final set S as small as possible.
The competition-enclaveless game number, or simply the enclaveless game number,
M. A. Henning and D. F. Rall: The enclaveless competition game 131
Ψ+g (G), of G is the number of vertices chosen when Maximizer starts the game and both
players play an optimal strategy according to the rules. The Minimizer-start competi-
tion-enclaveless game number, or simply the Minimizer-start enclaveless game number,
Ψ−g (G), of G is the number of vertices chosen when Minimizer starts the game and both
players play an optimal strategy according to the rules. The competition-enclaveless game,
which has been studied for example in [8, 9, 15, 16, 18], has not yet been explored in as
much depth as the domination game. In this paper we continue the study of the competition-
enclaveless game. Our main motivation for our study are the following conjectures that
have yet to be settled, where an isolate-free graph is a graph that does not contain an iso-
lated vertex.
Conjecture 1.2. If G is an isolate-free graph of order n, then Ψ+g (G) ≥ 12n.
Conjecture 1.2 was first posed as a question by Peter Slater to the 2nd author on 8th May
2015, and subsequently posed as a conjecture in [9]. We refer to Conjecture 1.2 for general
isolate-free graphs as the 12 -Enclaveless Game Conjecture. We also pose the following
conjecture for the Minimizer-start enclaveless game, where δ(G) denotes the minimum
degree of the graph G.
Conjecture 1.3. If G is a graph of order n with δ(G) ≥ 2, then Ψ−g (G) ≥ 12n.
We proceed as follows. By Observation 1.1, if the domination number of a graph is
known, then we immediately know the enclaveless number, and vice versa. In contrast,
we show in Section 2 that the game domination number and the enclaveless game number
are very different and are not related in the same way that the domination and enclaveless
numbers are related. Indeed, knowledge of the game domination number gives no informa-
tion of the enclaveless game number, and vice versa. We show that the domination game
and the enclaveless game are intrinsically different. In Section 3, we present fundamental
bounds on the enclaveless game number and the Minimizer-start enclaveless game number.
In Sections 4 and 5, we show that the 12 -Enclaveless Game Conjecture holds for regular
graphs and claw-free graphs, respectively. We use the standard notation [k] = {1, . . . , k}.
2 Game domination versus enclaveless game
Although the domination and enclaveless numbers of a graph G of order n are related by
the equation γ(G) +Ψ(G) = n (see Observation 1.1), as remarked in [9] the competition-
enclaveless game is very different from the domination game. To illustrate this, we present
two simple examples showing that the sum γg(G) + Ψ+g (G) on the class of graphs of a
fixed order can differ greatly even when restricted to trees.
For the first example, for k ≥ 3, let G be a tree with exactly two non-leaf vertices
both of which have k leaf neighbors, that is, G is a double star S(k, k). In this case,
Ψ+g (G) = Ψ
−
g (G) = k + 1 and γg(G) = 3 and γ
′
g(G) = 4. Thus if G is a double star of
order n, then γg(G) + Ψ+g (G) =
1
2n+ 3.
For the second example, we consider the class of paths; Pn denotes the path on n
vertices. For n ≥ 1, Košmrlj [14] showed that γ′g(Pn) =
⌈
n
2
⌉
and that γg(Pn) =
⌈
n
2
⌉
− 1
if n ≡ 3 (mod 4) and γg(Pn) =
⌈
n
2
⌉
, otherwise. For n ≥ 2, Phillips and Slater [16]
showed that Ψ+g (Pn) = ⌊ 3n+15 ⌋ and Ψ
−
g (Pn) = ⌊ 3n5 ⌋. Thus if G is a path Pn, then
γg(G) + Ψ
+
g (G) ≈ n+ 110n.
132 Ars Math. Contemp. 20 (2021) 129–142
The most important general fact in the domination game is the so-called Continuation
Principle, which provides a much-used monotonicity property of the game domination
number and allows us to assume that each optimal move of Dominator (and of Staller) is
taken from a restricted subset of the unchosen vertices. Due to its importance in the dom-
ination game, we recall this well-studied Continuation Principle. A partially dominated
graph is a graph together with a declaration that some vertices are already dominated and
need not be dominated, but can be played, in the rest of the game. Given a graph G and a
subset S of vertices of G, we denote by G|S the partially dominated graph with S as the
set of declared vertices already dominated. We use γg(G|S) (resp. γ′g(G|S)) to denote the
number of moves remaining in the game onG|S under optimal play when Dominator (resp.
Staller) has the next move. We are now in a position to state the Continuation Principle
presented by Kinnersley, West, and Zamani in [12, Lemma 2.1].
Lemma 2.1 (Continuation Principle). If G is a graph and A,B ⊆ V (G) with B ⊆ A,
then γg(G|A) ≤ γg(G|B) and γ′g(G|A) ≤ γ′g(G|B).
The Continuation Principle is one of the most important proof techniques to obtain
results on the domination game and its variants. It yields, for example, the following fun-
damental monotonicity property of the domination game; see [2, Theorem 6] and [12,
Corollary 4.1].
Theorem 2.2. The Dominator-start game domination number and the Staller-start game
domination number can differ by at most 1, that is, for any graph G, we have
|γg(G)− γ′g(G)| ≤ 1.
The most significant difference between the competition-enclaveless game and the
domination game is that the Continuation Principle holds for the domination game but
does not hold for the competition-enclaveless game. If the Continuation Principle were to
hold for the competition-enclaveless game, then this would imply that the Maximizer-start
enclaveless game number and the Minimizer-start enclaveless game number can differ by
at most 1. However, this is not the case, and these two game numbers can differ signifi-
cantly. For example, if n ≥ 1 and G is a star K1,n, then Ψ+g (G) = n while Ψ−g (G) = 1.
Thus, the numbers Ψ+g (G) and Ψ
−
g (G) can vary greatly.
Without the powerful proof method of the Continuation Principle at our disposal, the
competition-enclaveless game is raised to a greater level of difficulty than other domination
games played on graphs. Indeed, this suggests that there may exist a graph G (or infinite
classes of graphs) for which Ψ−g (G) > Ψ
+
g (G) is possible, and such that the difference
Ψ−g (G) − Ψ+g (G) can possibly be made arbitrarily large. However, we are unable at this
time to construct such examples, if they exist. Moreover, we are also unable to prove at this
time that Ψ−g (G) ≤ Ψ+g (G) is always true.
Another significant difference between the domination game and the competition-en-
claveless game is that upon completion of the domination game, the set of played vertices
is a dominating set although not necessarily a minimal dominating set, while upon com-
pletion of the competition-enclaveless game, the set of played vertices is always a maximal
enclaveless set. Thus, the enclaveless game numbers of a graph G are always squeezed
between the lower enclaveless number ψ(G) of G and the enclaveless number Ψ(G) of G.
We state this formally as follows.
M. A. Henning and D. F. Rall: The enclaveless competition game 133
Observation 2.3. If G is a graph, then
ψ(G) ≤ Ψ−g (G) ≤ Ψ(G) and ψ(G) ≤ Ψ+g (G) ≤ Ψ(G).
A graph G is well-dominated if all the minimal dominating sets of G have the same
cardinality. Examples of well-dominated graphs include, for example, the complete graph
Kn, C7, P4, the corona of any graph, and the graph formed from two vertex disjoint cycles
of order 5 joined by a single edge. Finbow, Hartnell and Nowakowski [7] characterized
the well-dominated graphs having no 3-cycle nor 4-cycle. As observed earlier, upon com-
pletion of the enclaveless game, the set of played vertices is always a maximal enclaveless
set. Hence, any sequence of legal moves by Maximizer and Minimizer (regardless of strat-
egy) in the enclaveless game played in a well-dominated graph of order n will always lead
to the game ending in n − γ(G) moves. Thus as a consequence of Observation 2.3, we
have the following interesting connection between the enclaveless game and the class of
well-dominated graphs.
Observation 2.4. If G is a well-dominated graph of order n, then
Ψ−g (G) = Ψ
+
g (G) = n− γ(G).
It is well-known that ifG is an isolate-free graph of order n, then γ(G) ≤ 12n, implying
by Observation 1.1 that Ψ(G) = n − γ(G) ≥ 12n. Hence one might think that γg(G) ≤
Ψ+g (G) for such a graph G with no isolated vertex. We now provide an infinite class of
graphs to show that the ratio γg/Ψ+g of these two graphical invariants can be strictly larger
than, and bounded away from, 1. The corona cor(G) of a graph G, also denoted G ◦K1 in
the literature, is the graph obtained from G by adding for each vertex v of G a new vertex
v′ and the edge vv′ (and so, the vertex v′ has degree 1 in cor(G)). The edge vv′ is called a
pendant edge. We shall need the following 2014 result due to Košmrlj [13].
Theorem 2.5 ([13, Theorem 4.1]). For k ≥ 1, if G = cor(Pk), then γg(G) = k + ⌈k−710 ⌉.
Let G be the (infinite) family of coronas of paths Pk where k ≥ 8 and kmod10 ∈
{8, 9}, that is,
G = {cor(Pk) : k mod 10 ∈ {8, 9}}.
As a consequence of Theorem 2.5, we have the following result.
Theorem 2.6. For every graph G ∈ G, we have
γg(G)
Ψ+g (G)
>
11
10
.
Proof. Let G ∈ G, and so G = cor(Pk) for some positive integer k where kmod10 ∈
{8, 9}. Every minimal dominating set of G has cardinality k, which implies by Observa-
tion 1.1 that every maximal enclaveless set of G also has cardinality k; that is, ψ(G) =
Ψ(G) = k where we recall that ψ(G) denotes the cardinality of the smallest maximal en-
claveless set in G and Ψ(G) is the cardinality of a largest enclaveless set in G. Hence by
Observation 2.3, Ψ+g (G) = k. Consequently, by Theorem 2.5 and since kmod10 ∈ {8, 9}
we have
γg(G)
Ψ+g (G)
=
k + ⌈k−710 ⌉
k
>
11
10
.
Hence, by Theorem 2.6, the difference γg(G) − Ψ+g (G) can be made arbitrarily large
for an infinite family of graphs.
134 Ars Math. Contemp. 20 (2021) 129–142
3 Fundamental bounds
In this section, we establish some fundamental bounds on the (Maximizer-start) enclaveless
game number and the Minimizer-start enclaveless game number. We establish next a lower
and upper bound on the enclaveless number of a graph in terms of the maximum degree
and order of the graph.
Proposition 3.1. If G is an isolate-free graph of order nwith maximum degree ∆(G) = ∆,
then (
1
∆ + 1
)
n ≤ ψ(G) ≤ Ψ(G) ≤
(
∆
∆+ 1
)
n.
Proof. If G is any graph of order n and maximum degree ∆, then γ(G) ≥ n∆+1 . Hence,
by Observation 1.1,
Ψ(G) = n− γ(G) ≤ n− n
∆+ 1
=
(
∆
∆+ 1
)
n.
On the other hand, let D be a minimal dominating set of maximum cardinality, and
so |D| = Γ(G). Let D = V (G) \ D, and so |D| = n − |D|. Let ℓ be the number of
edges between D and D. Since G is an isolate-free graph and D is a minimal dominating
set, every vertex in D has at least one neighbor in D, and so ℓ ≥ |D|. Since G has
maximum degree ∆, every vertex inD has at most ∆ neighbors inD, and so ℓ ≤ ∆ · |D| =
∆(n− |D|). Hence, |D| ≤ ∆(n− |D|), implying that Γ(G) = |D| ≤ ∆n/(∆+ 1). Thus
by Observation 1.1,
ψ(G) = n− Γ(G) ≥ n−
(
∆
∆+ 1
)
n =
(
1
∆ + 1
)
n.
This completes the proof of Proposition 3.1.
By Observation 2.3, the set of played vertices in either the Maximizer-start enclaveless
game or the Minimizer-start enclaveless game is a maximal enclaveless set of G. Thus as
an immediate consequence of Proposition 3.1, we have the following result.
Corollary 3.2. If G is an isolate-free graph of order n with maximum degree ∆(G) = ∆,
then(
1
∆ + 1
)
n ≤ Ψ−g (G) ≤
(
∆
∆+ 1
)
n and
(
1
∆ + 1
)
n ≤ Ψ+g (G) ≤
(
∆
∆+ 1
)
n.
We show that the upper bounds in Corollary 3.2 are realized for infinitely many con-
nected graphs.
Proposition 3.3. There exist infinitely many positive integers n along with a connected
graph G of order n satisfying
Ψ−g (G) = Ψ
+
g (G) =
(
∆(G)
∆(G) + 1
)
n.
Proof. Let r be an integer such that r ≥ 4 and let m be any positive integer. For each
i ∈ [m], let Hi be a graph obtained from a complete graph of order r + 1 by removing
M. A. Henning and D. F. Rall: The enclaveless competition game 135
the edge xiyi for two distinguished vertices xi and yi. The graph Fm is obtained from
the disjoint union of H1, . . . ,Hm by adding the edges yixi+1 for each i ∈ [m] where the
subscripts are computed modulo m. The vertices xi and yi are called connectors in Fm,
and each of the r − 1 vertices in the set V (Hi) \ {xi, yi} is called a hidden vertex of Hi.
Note that Fm is r-regular and has order n = m(r + 1).
We first show that Ψ−g (Fm) = (
r
r+1 )n. Suppose the Minimizer-start enclaveless game
is played on Fm. We provide a strategy for Maximizer that forces exactly rm vertices to be
played. Maximizer’s strategy is to make sure that all the connector vertices in the graph are
played. If he can accomplish this, then exactly rm vertices will be played when the game
ends because of the structure of Fm. Suppose that at some point in the game Minimizer
plays a vertex from some Hj . If one of the connector vertices, say xj , is playable, then
Maximizer responds by playing xj . If both connector vertices have already been played
and some hidden vertex, say w, in Hj is playable, then Maximizer plays w. If no vertex
of Hj is playable, then Maximizer plays a connector vertex from Hi for some i ̸= j if one
is playable and otherwise plays any playable vertex. Since Hk contains at least 3 hidden
vertices for each k ∈ [m], it follows that Maximizer can guarantee that all the connector
vertices are played by following this strategy. This implies that for each i ∈ [m], exactly
one hidden vertex of Hi is not played during the course of the game. That is, the set of
played vertices has cardinality
rm =
(
r
r + 1
)
m(r + 1) =
(
∆(Fm)
∆(Fm) + 1
)
n ,
where we recall that ∆(Fm) = r. Thus,
Ψ−g (Fm) ≥
(
∆(Fm)
∆(Fm) + 1
)
n.
By Corollary 3.2,
Ψ−g ((Fm)) ≤
(
∆(Fm)
∆(Fm) + 1
)
n.
Consequently, Ψ−g (Fm) =
(
∆(Fm)
∆(Fm)+1
)
n.
If the Maximizer-start enclaveless game is played on Fm, then the same strategy as
above for Maximizer forces rm vertices to be played (even with the relaxed condition that
r be an integer larger than 2). Thus as before, Ψ+g (Fm) =
(
∆(Fm)
∆(Fm)+1
)
n.
The lower bound in Corollary 3.2 on Ψ−g (G) is achieved, for example, by taking G =
K1,∆ for any given ∆ ≥ 1 in which case Ψ−g (G) = 1 = ( 1∆+1 )n where n = n(G) =
∆+ 1.
The lower bound in Corollary 3.2 on Ψ+g (G) is trivially achieved when ∆ = 1, in which
case G is the disjoint union of copies of K2. However, as remarked in the introductory
section, the main open problem in the competition-enclaveless game is the 12 -Enclaveless
Game Conjecture (stated formally in Conjecture 1.2) that claims that if G is an isolate-free
graph of order n, then Ψ+g (G) ≥ 12n. If the conjecture is true, then, from our earlier exam-
ples such as the double star, the bound is achieved for isolate-free graphs with arbitrarily
large maximum degree ∆.
136 Ars Math. Contemp. 20 (2021) 129–142
4 Regular graphs
In this section, we show that 12 -Enclaveless Game Conjecture (see Conjecture 1.2) holds
for the class of regular graphs, as does Conjecture 1.3 for the Minimizer-start enclaveless
game. For a set S ⊂ V (G) of vertices in a graph G and a vertex v ∈ S, we define the
S-external private neighborhood of a vertex v, abbreviated epnG(v, S), as the set of all
vertices outside S that are adjacent to v but to no other vertex of S; that is,
epnG(v, S) = {w ∈ V (G) \ S : NG(w) ∩ S = {v}}.
As remarked in the introduction, if the graph G is clear from the context, we omit the
subscript G in the above definitions. We define an S-external private neighbor of v to be a
vertex in epn(v, S).
We establish next a 12 -lower bound on Ψ
+
g (G) and Ψ
−
g (G) by forbidding induced stars
of a certain size. We remark that the proof of the following result uses similar counting
techniques to those employed by Southey and Henning in [20].
Proposition 4.1. If G is a graph with order n, minimum degree δ and with no induced
K1,δ+1, then ψ(G) ≥ 12n.
Proof. LetD be an arbitrary minimal dominating set ofG. Denote byD1 the set of vertices
in D that have a D-external private neighbor. That is, D1 = {x ∈ D : epn(x,D) ̸= ∅}.
In addition, let D2 = D \D1. Since D is a minimal dominating set, the set D2 consists of
those vertices in D that are isolated in the subgraph G[D] of G induced by D. Let
C1 =
⋃
x∈D1
epn(x,D) and C2 = V (G) \ (D ∪ C1).
We note that by definition, there are no edges in G joining a vertex in D2 and a vertex
in C1. That is, each vertex in D2 has at least δ neighbors in C2. Since the set D2 is
independent and G has no induced K1,δ+1, each vertex of C2 has at most δ neighbors in
D2. Denote by ℓ the number of edges of the form uv where u ∈ D2 and v ∈ C2. It now
follows that δ|D2| ≤ ℓ ≤ δ|C2|, that is, |D2| ≤ |C2|. Now,
|D| = |D1|+ |D2| ≤ |C1|+ |C2| = n− |D| ,
which shows that Γ(G) ≤ 12n. Hence by Observation 1.1, we have ψ(G) ≥
1
2n.
Observation 2.3 and Proposition 4.1 now yield the following result.
Corollary 4.2. If G is a graph with order n, minimum degree δ and with no induced
K1,δ+1, then Ψ+g (G) ≥ 12n and Ψ
−
g (G) ≥ 12n.
As a special case of Corollary 4.2, we have the desired 12 -lower bound on Ψ
+
g (G) and
Ψ−g (G) for regular graphs G without isolated vertices.
Corollary 4.3. If G is a regular graph of order n without isolated vertices, then Ψ+g (G) ≥
1
2n and Ψ
−
g (G) ≥ 12n.
We remark that if G is a graph of order n that is a disjoint union of copies of K2, then
Ψ+g (G) =
1
2n and Ψ
−
g (G) =
1
2n. The same conclusion holds if G is a disjoint union of
copies of C4. Hence, for k ∈ {1, 2} there are k-regular graphs G that achieve equality in
the lower bound in Corollary 4.3. However, it remains an open problem to characterize the
graphs achieving equality in Corollary 4.3 for each value of k ≥ 3.
M. A. Henning and D. F. Rall: The enclaveless competition game 137
5 Claw-free graphs
A graph is claw-free if it does not contain the star K1,3 as an induced subgraph. In this
section, we show that 12 -Enclaveless Game Conjecture (see Conjecture 1.2) holds for the
class of claw-free graphs with no isolated vertex, as does Conjecture 1.3 for the Minimizer-
start enclaveless game. For this purpose, we recall the definition of an irredundant set. For
a set S of vertices in a graph G and a vertex v ∈ S, the S-private neighborhood of v is the
set
pnG[v, S] = {w ∈ V : N [w] ∩ S = {v}}.
If the graph G is clear from context, we simply write pn[v, S] rather than pnG[v, S].
We note that epn(v, S) ⊆ pn[v, S] ⊆ epn(v, S) ∪ {v} and v ∈ pn[v, S] if and only if
v is isolated in G[S]. A vertex in the set pn[v, S] is called an S-private neighbor of v.
The set S is an irredundant set if every vertex of S has an S-private neighbor. The upper
irredundance number IR(G) is the maximum cardinality of an irredundant set in G.
The independence number α(G) of G is the maximal cardinality of an independent set
of vertices in G. An independent set of vertices of G of cardinality α(G) is called an α-set
of G. Every maximum independent set in a graph is a minimal dominating set, and every
minimal dominating set is an irredundant set. Hence we have the following inequality
chain.
Observation 5.1 ([5]). For every graph G, we have α(G) ≤ Γ(G) ≤ IR(G).
The inequality chain in Observation 5.1 is part of the canonical domination chain which
was first observed by Cockayne, Hedetniemi, and Miller [5] in 1978.
In 2004, Favaron [6] established the following upper bound on the upper irredundance
number of a claw-free graph.
Theorem 5.2 ([6]). If G is a connected, claw-free graph of order n, then IR(G) ≤
1
2 (n+ 1). Moreover, if IR(G) =
1
2 (n+ 1), then α(G) = Γ(G) = IR(G).
In addition, she proved the following stronger upper bound for the upper irredundance
number of claw-free graphs with minimum degree at least 2.
Corollary 5.3 ([6]). If G is a connected, claw-free graph of order n and minimum degree
at least 2, then IR(G) ≤ 12n.
Suppose that G is a claw-free graph of order n and minimum degree δ ≥ 2. By Corol-
lary 5.3, IR(G) ≤ 12n, and thus by Observations 1.1 and 5.1, we have
ψ(G) = n− Γ(G) ≥ n− IR(G) ≥ n− 1
2
n =
1
2
n.
By Observation 2.3, we therefore have the following result.
Theorem 5.4. If G is a claw-free graph of order n and δ(G) ≥ 2, then
Ψ+g (G) ≥
1
2
n and Ψ−g (G) ≥
1
2
n.
By Theorem 5.4, we note that Conjecture 1.3 holds for connected claw-free graphs.
In order to prove that Conjecture 1.2 holds for connected claw-free graphs, we need the
138 Ars Math. Contemp. 20 (2021) 129–142
characterization due to Favaron [6] of the graphs achieving equality in the bound of The-
orem 5.2. For this purpose, we recall that a vertex v of a graph G is a simplicial vertex if
its open neighborhood N(v) induces a complete subgraph of G. A clique of a graph G is a
maximal complete subgraph of G. The clique graph of G has the set of cliques of G as its
vertex set, and two vertices in the clique graph are adjacent if and only if they intersect as
cliques of G. A non-trivial tree is a tree of order at least 2.
Favaron [6] defined the family F of claw-free graphs G as follows. Let T1, . . . , Tq be
q ≥ 1 non-trivial trees. Let Li be the line graph of the corona cor(Ti) of the tree Ti for
i ∈ [q]. If q = 1, let G = L1. If q ≥ 2, let G be the graph constructed from the line graphs
L1, L2, . . . , Lq by choosing q − 1 pairs {xij , xji} such that the following holds.
• xij and xji are simplicial vertices of Li and Lj , respectively, where i ̸= j.
• The 2(q − 1) vertices from the q − 1 pairs {xij , xji} are all distinct vertices.
• Contracting each pair of vertices xij and xji into one common vertex cij results in a
graph whose clique graph is a tree.
To illustrate the above construction of a graph G in the family F consider, for example,
such a construction when q = 3 and the trees T1, T2, T3 are given in Figure 1.
c12 c23G
x12 x21 x23 x32L1 L2 L3⇓
cor(T1) cor(T2) cor(T3)⇓
T1 T2 T3⇓
Figure 1: An illustration of the construction of a graph G in the family F .
We note that if G is an arbitrary graph of order n in the family F , then n ≥ 3 is odd
and the vertex set of G can be partitioned into two sets A and B such that the following
holds.
• |A| = 12 (n− 1) and |B| =
1
2 (n+ 1).
• The set B is an independent set.
M. A. Henning and D. F. Rall: The enclaveless competition game 139
• Each vertex in A has exactly two neighbors in B.
We refer to the partition (A,B) as the partition associated withG. For the graphG ∈ F
illustrated in Figure 1, the set A consists of the darkened vertices and the set B consists of
the white vertices.
We are now in a position to state the characterization due to Favaron [6] of the graphs
achieving equality in the bound of Theorem 5.2.
Theorem 5.5 ([6]). If G is a connected, claw-free graph of order n ≥ 3, then IR(G) ≤
1
2 (n+ 1), with equality if and only if G ∈ F .
We prove next the following property of graphs in the family F .
Lemma 5.6. If G ∈ F and (A,B) is the partition associated with G, then the set B is the
unique IR-set of G.
Proof. We proceed by induction on the order n ≥ 3 of G ∈ F . If n = 3, then G = P3.
In this case, the set B consists of the two leaves of G, and the desired result is immediate.
This establishes the base case. Suppose that n ≥ 5 and that the result holds for all graphs
G′ ∈ F of order n′, where 3 ≤ n′ < n. Let Q be an IR-set of G.
By construction of the graph G, the set B contains at least two vertices of degree 1 in
G. Let v be an arbitrary vertex inB of degree 1 inG, and let u be its neighbor. We note that
u ∈ A. LetG′ = G−{u, v} and letG′ have order n′, and so n′ = n−2. LetA′ = A\{u}
and B′ = B \ {v}. By construction of the graph G and our choice of the vertex v, we note
that G′ ∈ F and that (A′, B′) is the partition associated with G′. Applying the inductive
hypothesis to G′, the set B′ is the unique IR-set of G′. Let w be the second neighbor of u
in G that belongs to the set B, and so N(u) ∩ B = {v, w}. By the structure of the graph
G ∈ F , we note thatN [w] ⊂ N [u] and that the subgraph ofG induced byN [w] is a clique.
Suppose, to the contrary, that Q ̸= B. Let Q′ be the restriction of Q to the graph
G′, and so Q′ = Q ∩ V (G′). Suppose that u ∈ Q. Since Q is an irredundant set, this
implies that v /∈ Q. If w ∈ Q, then pn[w,Q] = ∅, contradicting the fact that Q is an
irredundant set. Hence, w /∈ Q, and so Q′ ̸= B′. By the inductive hypothesis, the set Q′
is therefore not an IR-set of G′, and so |Q′| < IR(G′). Thus, IR(G) = |Q| = |Q′|+ 1 ≤
(IR(G′) − 1) + 1 = 12 (n
′ + 1) = 12 (n − 1) < IR(G), a contradiction. Hence, u /∈ Q. In
this case, IR(G) = |Q| ≤ |Q′|+ 1 ≤ IR(G′) + 1 = 12 (n
′ + 1) + 1 = 12 (n+ 1) = IR(G).
Hence, we must have equality throughout this inequality chain. This implies that v ∈ Q
and |Q′| = IR(G′). By the inductive hypothesis, we therefore have Q′ = B′. Hence,
Q = Q′ ∪ {v} = B′ ∪ {v} = B. Thus, the set B is the unique IR-set of G.
Corollary 5.7. If G ∈ F and (A,B) is the partition associated with G, then the set B is
the unique α-set of G and the unique Γ-set of G.
Proof. By Theorem 5.2, α(G) = Γ(G) = IR(G) = 12 (n + 1). By Lemma 5.6, the set B
is the unique IR-set of G. Since every α-set of G is an IR-set of G and α(G) = IR(G),
this implies that B is the unique α-set of G. Since every Γ-set of G is an IR-set of G and
Γ(G) = IR(G), this implies that B is the unique Γ-set of G.
We show next that Conjecture 1.2 holds for connected claw-free graphs.
Theorem 5.8. If G is a connected, claw-free graph of order n ≥ 2, then the following
holds.
140 Ars Math. Contemp. 20 (2021) 129–142
(a) Ψ+g (G) ≥ 12n.
(b) If G ̸= P3, then Ψ−g (G) ≥ 12n.
Proof. Let G be a connected, claw-free graph of order n ≥ 2. If IR(G) ≤ 12n, then
min{Ψ+g (G),Ψ−g (G)} ≥ ψ(G) ≥ n− IR(G) ≥
1
2
n.
Therefore, by Theorem 5.5, we can assume that IR(G) = 12 (n+1) andG ∈ F . Let (A,B)
be the partition associated with G. We show in this case we have min{Ψ+g (G),Ψ−g (G)} ≥
ψ(G) + 1.
By Observation 1.1, Γ(G) + ψ(G) = n. Moreover, the complement of every Γ-set
of G is a maximal enclaveless set, and the complement of every ψ-set of G is a minimal
dominating set. By Corollary 5.7, the set B is the unique Γ-set of G. These observations
imply that the complement of the set B, namely the set A, is the unique ψ-set of G. Thus
every maximal enclaveless set of G of cardinality ψ(G) is precisely the set A.
In the Maximizer-start enclaveless game played on G, Maximizer plays as his first
move any vertex from the set B. In the Minimizer-start enclaveless game played on G,
by supposition we have G ̸= P3, implying that there are at least two vertices in the set B
at distance at least 3 apart in G. Thus, whatever the first move is played by Minimizer,
Maximizer can always respond by playing as his first move a vertex chosen from the set
B. Hence, no matter who starts the game, Maximizer can play a vertex in B as his first
move. Thus if S denotes the set of all vertices played when the game ends (in either game),
then the set S is a maximal enclaveless set in G. By our earlier observations, such a set
S contains a vertex of B and is therefore different from the set A. Since the set A is the
unique ψ-set of G, this implies that |S| > ψ(G). Therefore,
|S| ≥ ψ(G) + 1 = (n− Γ(G)) + 1 = n− 1
2
(n+ 1) + 1 =
1
2
(n+ 1).
Since the first move of Maximizer from the set B may not be an optimal move, we
have that Ψ+g (G) ≥ ψ(G) + 1 if we are playing the Maximizer-start enclaveless game and
Ψ−g (G) ≥ ψ(G) + 1 if we are playing the Minimizer-start enclaveless game. Thus, in both
games Maximizer has a strategy to finish the game in at least 12 (n+1) moves. Hence, if we
assume that IR(G) = 12 (n+ 1), then Ψ
+
g (G) ≥ min{Ψ+g (G),Ψ−g (G)} ≥ 12 (n+ 1).
By Theorem 5.8(a), we note that Conjecture 1.2 holds for connected claw-free graphs.
Moreover by Theorem 5.8(b), we note that Conjecture 1.3 holds for connected claw-free
graphs even if we relax the minimum degree two condition and replace it with the require-
ment that the graph is isolate-free and different from the path P3.
6 Open problems and conjectures
In this paper, we have shown that the 12 -Enclaveless Game Conjecture (see, Conjecture 1.2)
is true for special classes of graphs, such as regular graphs and claw-free graphs. However,
the conjecture has yet to be solved in general. It would be very interesting to prove or dis-
prove the conjecture, or at least prove the conjecture for certain other important classes of
graphs. We have also shown that the related conjecture for the Minimizer-start enclaveless
game (see, Conjecture 1.3) holds for special classes. Again, it would be interesting to make
M. A. Henning and D. F. Rall: The enclaveless competition game 141
further inroads into the conjecture. We close with the following two questions that we have
yet to settle.
Question 6.1. Do there exist graphs G such that Ψ−g (G) > Ψ+g (G)? If so, how large can
the difference Ψ−g (G)−Ψ+g (G) be made? Or is Ψ−g (G) ≤ Ψ+g (G) always true?
Question 6.2. Is it possible to characterize graphs G such that Ψ−g (G) = Ψ+g (G)?
ORCID iDs
Michael A. Henning https://orcid.org/0000-0001-8185-067X
Douglas F. Rall https://orcid.org/0000-0002-5482-756X
References
[1] B. Brešar, M. A. Henning, S. Klavžar and D. F. Rall, Domination Games Played on Graphs,
SpringerBriefs in Mathematics, Springer, 2021, doi:10.1007/978-3-030-69087-8.
[2] B. Brešar, S. Klavžar and D. F. Rall, Domination game and an imagination strategy, SIAM J.
Discrete Math. 24 (2010), 979–991, doi:10.1137/100786800.
[3] C. Bujtás, Domination game on forests, Discrete Math. 338 (2015), 2220–2228, doi:10.1016/j.
disc.2015.05.022.
[4] C. Bujtás, On the game domination number of graphs with given minimum degree, Electron. J.
Combin. 22 (2015), #P3.29 (18 pages), doi:10.37236/4497.
[5] E. J. Cockayne, S. T. Hedetniemi and D. J. Miller, Properties of hereditary hypergraphs and
middle graphs, Canad. Math. Bull. 21 (1978), 461–468, doi:10.4153/cmb-1978-079-5.
[6] O. Favaron, Independence and upper irredundance in claw-free graphs, Discrete Appl. Math.
132 (2003), 85–95, doi:10.1016/s0166-218x(03)00392-5.
[7] A. Finbow, B. Hartnell and R. Nowakowski, Well-dominated graphs: a collection of well-
covered ones, Ars Combin. 25 (1988), 5–10.
[8] W. Goddard and M. A. Henning, The competition-independence game in trees, J. Combin.
Math. Combin. Comput. 104 (2018), 161–170.
[9] M. A. Henning, My favorite domination game conjectures, in: R. Gera, T. W. Haynes and S. T.
Hedetniemi (eds.), Graph Theory: Favorite Conjectures and Open Problems – 2, Springer,
Cham, Problem Books in Mathematics, pp. 135–148, 2018, doi:10.1007/978-3-319-97686-0
12.
[10] M. A. Henning and W. B. Kinnersley, Domination game: a proof of the 3/5-conjecture for
graphs with minimum degree at least two, SIAM J. Discrete Math. 30 (2016), 20–35, doi:
10.1137/140976935.
[11] M. A. Henning and C. Löwenstein, Domination game: extremal families for the 3/5-conjecture
for forests, Discuss. Math. Graph Theory 37 (2017), 369–381, doi:10.7151/dmgt.1931.
[12] W. B. Kinnersley, D. B. West and R. Zamani, Extremal problems for game domination number,
SIAM J. Discrete Math. 27 (2013), 2090–2107, doi:10.1137/120884742.
[13] G. Košmrlj, Realizations of the game domination number, J. Comb. Optim. 28 (2014), 447–461,
doi:10.1007/s10878-012-9572-x.
[14] G. Košmrlj, Domination game on paths and cycles, Ars Math. Contemp. 13 (2017), 125–136,
doi:10.26493/1855-3974.891.e93.
142 Ars Math. Contemp. 20 (2021) 129–142
[15] J. B. Phillips and P. J. Slater, An introduction to graph competition independence and enclave-
less parameters, Graph Theory Notes N. Y. 41 (2001), 37–41.
[16] J. B. Phillips and P. J. Slater, Graph competition independence and enclaveless parameters,
in: Proceedings of the Thirty-third Southeastern International Conference on Combinatorics,
Graph Theory and Computing (Boca Raton, FL, 2002), volume 154, 2002 pp. 79–100.
[17] S. Schmidt, The 3/5-conjecture for weakly S(K1,3)-free forests, Discrete Math. 339 (2016),
2767–2774, doi:10.1016/j.disc.2016.05.017.
[18] S. J. Seo and P. J. Slater, Competition parameters of a graph, AKCE Int. J. Graphs Comb. 4
(2007), 183–190.
[19] P. J. Slater, Enclaveless sets and MK-systems, J. Res. Nat. Bur. Standards 82 (1977), 197–202,
doi:10.6028/jres.082.019.
[20] J. Southey and M. A. Henning, Edge weighting functions on dominating sets, J. Graph Theory
72 (2013), 346–360, doi:10.1002/jgt.21649.