# On the coalition number of trees

1Davood Bakhshesh, 2Michael A. Henning, and 3Dinabandhu Pradhan

1Department of Computer Science
University of Bojnord
Bojnord, Iran
Email<EMAIL_ADDRESS>

2Department of Mathematics and Applied Mathematics
University of Johannesburg
Auckland Park, 2006 South Africa
Email<EMAIL_ADDRESS>

3Department of Mathematics and Computing
Indian Institute of Technology (ISM)
Dhanbad, India
Email<EMAIL_ADDRESS>Research supported in part by the University of
Johannesburg.Corresponding author.

###### Abstract

Let $G$ be a graph with vertex set $V$ and of order $n=|V|$, and let
$\delta(G)$ and $\Delta(G)$ be the minimum and maximum degree of $G$,
respectively. Two disjoint sets $V_{1},V_{2}\subseteq V$ form a coalition in
$G$ if none of them is a dominating set of $G$ but their union $V_{1}\cup
V_{2}$ is. A vertex partition $\Psi=\\{V_{1},\ldots,V_{k}\\}$ of $V$ is a
coalition partition of $G$ if every set $V_{i}\in\Psi$ is either a dominating
set of $G$ with the cardinality $|V_{i}|=1$, or is not a dominating set but
for some $V_{j}\in\Psi$, $V_{i}$ and $V_{j}$ form a coalition. The maximum
cardinality of a coalition partition of $G$ is the coalition number
$\mathcal{C}(G)$ of $G$. Given a coalition partition
$\Psi=\\{V_{1},\ldots,V_{k}\\}$ of $G$, a coalition graph ${\rm CG}(G,\Psi)$
is associated on $\Psi$ such that there is a one-to-one correspondence between
its vertices and the members of $\Psi$, where two vertices of ${\rm
CG}(G,\Psi)$ are adjacent if and only if the corresponding sets form a
coalition in $G$. In this paper, we partially solve one of the open problems
posed in Haynes et al. [1] and we solve two open problems posed by Haynes et
al. [2]. We characterize all graphs $G$ with $\delta(G)\leq 1$ and
$\mathcal{C}(G)=n$, and we characterize all trees $T$ with
$\mathcal{C}(T)=n-1$. We determine the number of coalition graphs that can be
defined by all coalition partitions of a given path. Furthermore, we show that
there is no universal coalition path, a path whose coalition partitions
defines all possible coalition graphs.

Keywords: Coalition number; Domination number; Coalition partition; Coalition
graphs.
AMS subject classification: 05C69

##  1 Introduction

Let $G$ be a graph with vertex set $V=V(G)$. Throughout this paper, we only
consider graphs without multiple edges and loops. Two vertices are _neighbors_
if they are adjacent. 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$,
where a vertex _dominates_ itself and its neighbors. Equivalently, $S\subseteq
V$ is a dominating set of $G$ if every vertex of $V\setminus S$ is adjacent to
a vertex of $S$. The minimum cardinality of a dominating set of $G$ is the
_domination number_ of $G$, denoted by $\gamma(G)$. If $X,Y\subseteq V(G)$,
then the set $X$ _dominates_ the set $Y$ if every vertex in $Y$ is dominated
by at least one vertex in $X$. We refer the reader to the books [5, 6] to
study an overview of dominating sets in graphs.

In 2020, Haynes, Hedetniemi, Hedetniemi, McRae, and Mohan [1] presented a
graph theoretic model of a coalition, and introduced the concept of a
_coalition_ in graphs. They defined a pair of sets $V_{1},V_{2}\subseteq V$ to
be a _coalition_ in $G$ if none of them is a dominating set of $G$ but
$V_{1}\cup V_{2}$ is. Such a pair $V_{1}$ and $V_{2}$ is said to _form a
coalition_ , and are called _coalition partners_. A vertex partition
$\Psi=\\{V_{1},\ldots,V_{k}\\}$ of $V$ is a _coalition partition_ of $G$,
abbreviated a $c$-_partition_ in [1], if every set $V_{i}\in\Psi$ is either a
dominating set of $G$ with cardinality $|V_{i}|=1$, or is not a dominating set
but for some $V_{j}\in\Psi$, $V_{i}$ and $V_{j}$ form a coalition. The maximum
cardinality of a coalition partition of $G$ is called the _coalition number_
of $G$, denoted by $\mathcal{C}(G)$. A coalition partition of $G$ of
cardinality $\mathcal{C}(G)$ is called a _$\mathcal{C}$ -partition of $G$_. A
motivation of this graph theory model of a coalition is given by Haynes et al.
in their series of papers on coalitions in [1, 2, 3, 4].

Given a coalition partition $\Psi=\\{V_{1},\ldots,V_{k}\\}$ of $G$, a
coalition graph ${\rm CG}(G,\Psi)$ is associated on $\Psi$ such that there is
a one-to-one correspondence between its vertices and the members of $\Psi$,
where two vertices of ${\rm CG}(G,\Psi)$ are adjacent if and only if the
corresponding sets form a coalition in $G$.

For notation and graph theory terminology not defined herein, we in general
follow [7]. Specifically, let $G$ be a graph with vertex set $V(G)$ and edge
set $E(G)$, and of order $n(G)=|V(G)|$ and size $m(G)=|E(G)|$. For a set of
vertices $S\subseteq V(G)$, the subgraph induced by $S$ is denoted by $G[S]$.
Two vertices in $G$ are _neighbors_ if they are adjacent. The _open
neighborhood_ $N_{G}(v)$ of a vertex $v$ in $G$ is the set of neighbors of
$v$, while the _closed neighborhood_ of $v$ is the set $N_{G}[v]=\\{v\\}\cup
N(v)$. We denote the _degree_ of $v$ in $G$ by $\deg_{G}(v)=|N_{G}(v)|$. The
minimum and maximum degree in $G$ is denoted by $\delta(G)$ and $\Delta(G)$,
respectively. An _isolated vertex_ is a vertex of degree $0$, and an _isolate_
-_free graph_ is a graph that contains no isolated vertex. A vertex of degree
$1$ is called a _leaf_ , and its unique neighbor a _support vertex_. A graph
is _isolate_ -_free_ if it contains no isolated vertex. A vertex of degree
$n(G)-1$ in $G$ is a _universal vertex_ , also called a _full vertex_ in the
literature, of $G$. For a set $S\subseteq V(G)$, its _open neighborhood_ is
the set $N_{G}(S)=\cup_{v\in S}N_{G}(v)$, and its _closed neighborhood_ is the
set $N_{G}[S]=N_{G}(S)\cup S$. If the graph $G$ is clear from the context, we
omit writing it in the above expressions. For example, we simply write $V$,
$E$, $n$, $m$, $N(v)$ and $N(S)$ rather than $V(G)$, $E(G)$, $n(G)$, $m(G)$,
$N_{G}(v)$ and $N_{G}(S)$, respectively.

A _vertex cover_ of a graph $G$ is a set $S$ of vertices such that every edge
in $E(G)$ is incident with at least one vertex in $S$. The _vertex covering
number_ $\beta(G)$, also denoted $\tau(G)$ in the literature, is the minimum
cardinality of a vertex cover of $G$. For a positive integer $k$, we let
$[k]=\\{1,\ldots,k\\}$.

###  1.1 Motivation and known results

In this paper, we continue the study of coalitions in graphs. Our immediate
aim is to answer, in part or fully, the following intriguing problems posed by
the Haynes et al. in their recent series of paper given in [1, 2, 3]. Haynes
et al. [1] posed the following open problem.

###### Problem 1

([1]) Characterize the graphs $G$ satisfying $\mathcal{C}(G)=n(G)$.

For $r,s\geq 1$, a _double star_ $S(r,s)$ is a tree with exactly two
(adjacent) vertices that are not leaves, with one of the vertices having $r$
leaf neighbors and the other $s$ leaf neighbors. The double star $S(2,2)$, for
example, is illustrated in Figure 1(a). The bull graph $B$, illustrated in
Figure 1(b), is a graph obtained from a triangle by adding two disjoint
pendant edges. Let $F_{1}$ be obtained from a bull graph by deleting one of
the vertices of degree $1$, and let $F_{2}$ be obtained from a $4$-cycle by
adding a pendant edges. The graphs $F_{1}$ and $F_{2}$ are illustrated in
Figures 1(c) and 1(d), respectively.

(a) $S(2,2)$(b) $B_{1}$(c) $F_{1}$(d) $F_{2}$ Figure 1: Four graphs of small
orders

Let $\cal F$ be a family of graphs consisting of 18 graphs: $K_{1}$, $K_{2}$,
$\overline{K_{2}}$, $K_{1}\cup K_{2}$, $P_{3}$, $K_{3}$, $K_{1,3}$, $2K_{2}$,
$P_{4}$, $C_{4}$, $F_{1}$, $K_{4}-e$, $P_{2}\cup P_{3}$, $F_{2}$, $B_{1}$,
$P_{5}$, $S(1,2)$, and $S(2,2)$. Haynes et al. [2] proved the following
result.

###### Theorem 1

([2]) If $\Psi$ is a coalition partition of a path $P_{k}$, then ${\rm
CG}(P_{k},\Psi)\in{\cal F}$.

A path is called a _universal coalition path_ if all 18 graphs of $\cal F$ can
be defined by the coalition partitions of the path. Haynes et al. [2] posed
the following two open problems.

###### Problem 2

([2]) Given a positive integer $k$, how many coalition graphs can be defined
by the coalition partitions of a path $P_{k}$?

###### Problem 3

([2]) Does there exist a positive integer $k$ such that all 18 graphs of $\cal
F$ can be defined by the coalition partitions of $P_{k}$? If so, what is the
smallest universal coalition path?

In this paper, we characterize all graphs $G$ with $\delta(G)=1$ and
$\mathcal{C}(G)=n$. Moreover, we characterize all trees $T$ with
$\mathcal{C}(T)=n$ and all trees $T$ with $\mathcal{C}(T)=n-1$. This solves
part of Problem 1. On the other hand, we solve Problem 2 and Problem 3. In
particular, we theoretically and empirically determine the number of coalition
graphs that can be defined by the coalition partitions of path $P_{k}$.
Consequently, we show that there is no universal coalition path.

The coalition number of a path and a cycle is determined in [1].

###### Theorem 2

([1]) The following hold for a path $P_{n}$ and a cycle $C_{n}$.

  1. (a)

$C(P_{n})=n$ if $n\leq 4$, $C(P_{n})=4$ if $n=5$, $C(P_{n})=5$ if $6\leq n\leq
9$, and $C(P_{n})=6$ if $n\geq 10$.

  2. (b)

$C(C_{n})=n$ if $3\leq n\leq 6$, $C(C_{n})=5$ if $n=7$, and $C(C_{n})=6$ if
$n\geq 8$.

As consequence of Theorem 2, we have the following result.

###### Corollary 1

([1]) If $G$ is a path or a cycle, then $C(G)\leq 6$.

We shall need the following properties of a $c$-partition in a graph.

###### Proposition 1

([1]) If $\Psi$ is a $c$-partition of a graph $G$, then $\Delta({\rm
CG}(G,\Psi))\leq\Delta(G)+1$.

By Proposition 1, if $\Psi$ is a $c$-partition of a graph $G$ and $S\in\Psi$,
then $S$ is in at most $\Delta(G)+1$ coalitions in $\Psi$. The following
result is stated without proof in [3]. For completeness we present a proof of
this elementary property of a $c$-partition in a graph.

###### Proposition 2

([3]) If $\Psi$ is a $c$-partition of a graph $G$ and $v$ is an arbitrary
vertex of $G$, then $\beta({\rm CG}(G,\Psi))\leq\deg_{G}(v)+1$.

Proof.  Let $G$ with a graph with $c$-partition
$\Psi=\\{V_{1},V_{2},\ldots,V_{k}\\}$, and let $v\in V(G)$. Let
$\Psi^{\prime}$ be a subset of $\Psi$, such that $V_{i}\in\Psi^{\prime}$ if
and only if $V_{i}$ contains a vertex of $N[v]$. Hence,
$|\Psi^{\prime}|\leq|N[v]|=\deg_{G}(v)+1$. Now consider an arbitrary edge
$V_{i}V_{j}$ in ${\rm CG}(G,\Psi)$. Since the set $V_{i}\cup V_{j}$ is a
dominating set of $G$, at least one of $V_{i}$ and $V_{j}$ contains a vertex
from $N[v]$ in $G$. Thus, at least one of $V_{i}$ and $V_{j}$ is in
$\Psi^{\prime}$. Hence, $\Psi^{\prime}$ is a vertex cover of ${\rm
CG}(G,\Psi)$, and so $\beta({\rm
CG}(G,\Psi))\leq|\Psi^{\prime}|\leq\deg_{G}(v)+1$. $\Box$

The following upper bounds on the coalition number of a graph are established
in [3].

###### Theorem 3

([3]) If $G$ is a graph with $\delta=\delta(G)$ and $\Delta=\Delta(G)$, then
the following hold.

  1. (a)

$C(G)\leq\frac{1}{4}(\Delta+3)^{2}$.

  2. (b)

If $\delta<\frac{1}{2}\Delta$, then $C(G)\leq(\delta+1)(\Delta-\delta+2)$.

As a consequence of Corollary 1 and Theorem 3(b), we have the following
result.

###### Corollary 2

([1, 3]) If $G$ is a graph with $\delta(G)=1$, then $C(G)\leq 2(\Delta(G)+1)$.

##  2 Trees with $\mathcal{C}(T)=n$

In this section, we characterize trees $T$ of order $n$ satisfying $C(T)=n$.
First we characterize graphs $G$ of order $n$ and $\delta(G)=0$ such that
$\mathcal{C}(G)=n$.

###### Theorem 4

If $G$ is a graph of order $n$ with $\delta(G)=0$, then $\mathcal{C}(G)=n$ if
and only if $G\cong K_{1}\cup K_{n-1}$.

Proof.  Clearly, $\mathcal{C}(K_{1}\cup K_{n-1})=n$. Conversely, suppose that
$G$ is a graph of order $n$ with $\delta(G)=0$ and $\mathcal{C}(G)=n$. Thus,
$\\{\\{v\\}\colon v\in V(G)\\}$ is a $\mathcal{C}$-partition of $G$. Let $x$
be an isolated vertex of $G$. If $v$ and $v^{\prime}$ are two distinct
vertices in $V(G)\backslash\\{x\\}$, then since the set $\\{v,v^{\prime}\\}$
does not dominate the graph $G$, the pair $\\{v\\}$ and $\\{v^{\prime}\\}$ do
not form a coalition. Therefore, $\\{v\\}$ and $\\{x\\}$ form a coalition for
each $v\in V(G)\backslash\\{x\\}$, implying that $V(G)\backslash\\{x\\}$ is a
clique in $G$ of cardinality $n-1$. Thus, $G\cong K_{1}\cup K_{n-1}$. $\Box$

We next define a family $\mathcal{F}_{1}$ of graphs.

###### Definition 1

(The family $\mathcal{F}_{1}$) Let $G$ be an isolate-free graph constructed as
follows. Let $V(G)=\\{x,y,w\\}\cup P\cup Q$, where $P\cap
Q\cap\\{x,y,w\\}=\emptyset$ and $|P\cup Q|\geq 1$. Further, if
$Q\neq\emptyset$, then $|Q|\geq 2$. Let the edge set $E(G)$ be defined as
follows. Let $N_{G}(x)=\\{y\\}$ and let $N_{G}(w)=P\cup Q$. Join each vertex
$p\in P$ to every vertex in $(P\cup Q)\setminus\\{p\\}$. If $Q\neq\emptyset$,
then add all edges from the vertex $y$ to every vertex in $Q$, and so
$Q\cup\\{x\\}\subseteq N_{G}(y)$. Further if $Q\neq\emptyset$, then add edges
between vertices in $Q$, including the possibility of adding no edge (in which
case $Q$ is an independent set), in such a way that $G[Q]$ does not contain a
full vertex. Thus, every vertex $q\in Q$ is not adjacent in $G$ to at least
one vertex in $Q\setminus\\{q\\}$. Finally, add any number of edges between
the vertex $y$ and vertices in $P$, including the possibility of adding no
edge between $y$ and vertices in $P$.

We note that if $G\in\mathcal{F}_{1}$ is a disconnected graph of order $n$,
then $G\cong K_{2}\cup K_{n-2}$. We are now in a position to characterize
graphs $G$ of order $n$ with $\delta(G)=1$ and with no full vertex that
satisfy $\mathcal{C}(G)=n$.

###### Theorem 5

If $G$ is a graph of order $n$ with $\delta(G)=1$ and with no full vertex,
then $\mathcal{C}(G)=n$ if and only if $G\in{\cal F}_{1}$.

Proof.  Suppose firstly that $G\in{\cal F}_{1}$. Adopting our notation in
Definition 1, we have that if $p\in P\cup\\{w\\}$, then $\\{x,p\\}$ is a
dominating set of $G$, and if $q\in Q\cup\\{w\\}$, then $\\{y,q\\}$ is a
dominating set of $G$, implying that every subset $\\{v\\}$, where $v\in
N[w]$, forms a coalition with $\\{x\\}$ or $\\{y\\}$. Therefore,
$\mathcal{C}(G)=n$.

Conversely, let $G$ be a graph of order $n$ with $\delta(G)=1$ and with no
full vertex, and suppose that $\mathcal{C}(G)=n$. Let $x$ be a leaf of $G$ and
let $y$ be the unique neighbor of $x$ in $G$. Let $\Psi$ be a
$\mathcal{C}$-partition of $G$, and so $|\Psi|=n$ and $\Psi$ is a
$c$-partition of $G$. Thus, each member of $\Psi$ is a singleton set (of
cardinality $1$), that is, if $v\in V(G)$, then $\\{v\\}\in\Psi$. We show that
$G\in{\cal F}_{1}$. We know that $\\{x\\}\in\Psi$ and $\\{y\\}\in\Psi$.
Suppose that $\\{x\\}$ and $\\{y\\}$ form a coalition in $G$. Since $x$ is a
leaf and $N(x)=\\{y\\}$, all members of $V\setminus\\{x,y\\}$ must be adjacent
to $y$. Thus, the degree of $y$ is $n-1$, and so $y$ is a full vertex of $G$,
a contradiction. Hence, $\\{x\\}$ and $\\{y\\}$ do not form a coalition. Let
$w$ be a vertex not dominated by $y$, and so $w\neq y$ and $w$ is not adjacent
to $y$. Let $N(w)=\\{w_{1},\dots,w_{k}\\}$.

We show that $V=\\{x,y\\}\cup N[w]$. Suppose, to the contrary, that there
exists a vertex $v\in V\backslash(\\{x,y\\}\cup N[w])$. If $z$ is an arbitrary
vertex distinct from $x$ and $y$, then the pair $\\{v\\}$ and $\\{z\\}$ do not
form a coalition since the vertex $x$ is not dominated by the set $\\{v,z\\}$.
Moreover, $\\{v\\}$ does not form a coalition with $\\{x\\}$ or $\\{y\\}$
since the vertex $w$ is not dominated by the set $\\{v,x,y\\}$. Hence,
$\\{v\\}$ has no coalition partner, a contradiction. Therefore,
$V=\\{x,y\\}\cup N[w]$. Recall that $w\neq y$ and $w$ is not adjacent to $y$.
Since $G$ has no full vertices, every set of $\Psi$ must be a coalition
partner of some other set of $\Psi$. Let

${\cal W}=\\{S\in\Psi\colon N[w]\cap S\neq\emptyset\\}.$

Since $\mathcal{C}(G)=n$, we note that ${\cal
W}=\left\\{\\{w\\},\\{w_{1}\\},\ldots,\\{w_{k}\\}\right\\}$. Necessarily, each
member of $\cal W$ forms a coalition with $\\{x\\}$ or $\\{y\\}$, and there is
no coalition between the members of $\cal W$. In particular, $\\{w\\}$ is a
coalition partner of each of $\\{x\\}$ and $\\{y\\}$. Let ${\cal
W}_{P}\subseteq{\cal W}\setminus\left\\{\\{w\\}\right\\}$ be the collection of
all sets of $\Psi$ that form a coalition with $\\{x\\}$, and let $P=\\{p\in
N(w)\colon\\{p\\}\in{\cal W}_{P}\\}$. Moreover, let ${\cal W}_{Q}=\left({\cal
W}\setminus\left\\{\\{w\\}\right\\}\right)\setminus{\cal W}_{P}$ and let
$Q=\\{q\in N(w)\colon\\{q\\}\in{\cal W}_{Q}\\}$. We note that $\\{P,Q\\}$ is a
weak partition of $N(w)$, that is, $N(w)=P\cup Q$, where $P\cap Q=\emptyset$
and where in a weak partition we allow some of the sets in the partition to be
empty (in our case, possibly $P=\emptyset$ or $Q=\emptyset$). No set in ${\cal
W}_{Q}$ forms a coalition with $\\{x\\}$, and therefore every member of ${\cal
W}_{Q}$ forms a coalition with $\\{y\\}$.

Let $p\in P$. Thus, $\\{p\\}\in{\cal W}_{P}$ forms a coalition with $\\{x\\}$,
and so the set $\\{x,p\\}$ is a dominating set of $G$, implying that the
vertex $p$ dominates the set $N[w]$, and so $p$ is adjacent to every vertex in
$N(w)\backslash\\{p\\}$. Let $q\in Q$. Thus, $\\{q\\}\in{\cal W}_{Q}$ and the
set $\\{x,q\\}$ is not a dominating set of $G$, implying that the vertex $q$
is not adjacent to at least one vertex in $N(w)\setminus\\{q\\}$. As observed
earlier, every vertex in $P$ is adjacent to every vertex in $N(w)=P\cup Q$,
implying that all non-neighbors of $q$ in $N(w)$ belong to the set $Q$.
Further, since $\\{q,y\\}$ is a dominating set of $G$, the vertex $y$ is
adjacent to every vertex in $Q$ that is not adjacent to $q$. In particular, if
$q^{\prime}$ is a vertex in $Q\setminus\\{q\\}$ that is not adjacent to $q$,
then since $\\{y,q^{\prime}\\}$ is a dominating set of $G$, the vertex $y$ is
adjacent to the vertex $q$. Therefore, the vertex $y$ dominates the set $Q$.
According to the definition of family ${\cal F}_{1}$, we infer that $G\in{\cal
F}_{1}$. $\Box$

Next we characterize graphs $G$ of order $n$ with $\delta(G)=1$ and exactly
one full vertex that satisfy $\mathcal{C}(G)=n$.

###### Theorem 6

If $G$ is a graph of order $n\geq 3$ with $\delta(G)=1$ and with exactly one
full vertex, then $\mathcal{C}(G)=n$ if and only if $G$ is obtained from the
graph $K_{1}\cup K_{n-1}$ by adding an edge joining the isolated vertex to an
arbitrary vertex of the complete graph $K_{n-1}$.

Proof.  For $n\geq 3$, let $G$ be obtained from $K_{1}\cup K_{n-1}$ by adding
an edge $xy$ where $x$ is the vertex in the copy of $K_{1}$ and $y$ is a
vertex in the complete graph $K_{n-1}$. In the resulting graph $G$, the vertex
$x$ has degree $1$ and the vertex $y$ has degree $n-1$. Thus, $y$ is a full
vertex. If $w\in V(G)\setminus\\{x,y\\}$, then $\\{w,x\\}$ is a dominating set
of $G$, and so $\\{w\\}$ forms a coalition with the set $\\{x\\}$, implying
that $\mathcal{C}(G)=n$. This proves the sufficiency.

To prove the necessity, let $G$ be a graph of order $n\geq 3$ with
$\delta(G)=1$ and with exactly one full vertex and suppose that
$\mathcal{C}(G)=n$. Let $\Psi$ be a $\mathcal{C}$-partition of $G$. Let $u$
and $v$ be vertices of $G$ where $\deg_{G}(u)=1$ and $\deg_{G}(v)=n-1$, and
let $w$ be an arbitrary vertex in $V(G)\setminus\\{u,v\\}$. Since $v$ is a
full vertex, the set $\\{v\\}$ does not form a coalition with any vertex of
$G$. Hence since the set $\\{w\\}$ is not a dominating set of $G$, the only
coalition partner of the set $\\{w\\}$ in $\Psi$ is the set $\\{u\\}$. This
implies that the vertex $w$ is adjacent to every vertex in $G$ except for the
vertex $u$. This is true for all vertices $w\in V(G)\setminus\\{u,v\\}$,
implying that the graph $G^{\prime}=G-v\cong K_{1}\cup K_{n-2}$. Rebuilding
the graph $G$ from $G^{\prime}$ by adding back the vertex $y$ and all edges
joining $y$ to the $n-1$ vertices in $V(G^{\prime})$, the desired result
follows. $\Box$

We are now in a position to characterize all trees $T$ of order $n$ with
$\mathcal{C}(T)=n$.

###### Theorem 7

If $T$ is a tree of order $n$, then $\mathcal{C}(T)=n$ if and only if $T$ is a
path of order at most $4$.

Proof.  By Theorem 2(a), if $T=P_{n}$ where $n\in[4]$, then $C(P_{n})=n$.
Conversely, let $T$ be a tree of order $n$ satisfying $\mathcal{C}(T)=n$. The
result is immediate if $n=1$ or $n=2$, and so we may assume that $n\geq 3$. If
there is a full vertex in $T$, then $T\cong K_{1,n-1}$. In this case, by
Theorem 6 we must have that $n=3$, yielding $T=P_{3}$, as desired. Hence we
may assume that $T$ does not have a full vertex, implying that $n\geq 4$. In
this case by Theorem 5, the tree $T$ belongs to the family ${\cal F}_{1}$.
Adopting our earlier notation in Definition 1, if $Q\neq\emptyset$, then
$|Q|\geq 2$, and the graph $T[\\{y,q_{1},q_{2},w\\}]$ contains a $4$-cycle
where $\\{q_{1},q_{2}\\}\subseteq Q$, contradicting the fact that $T$ is a
tree. Hence, $Q=\emptyset$. If $|P|\geq 2$, then the graph $T[P\cup\\{w\\}]$
contains a copy of $K_{3}$, once again contradicting the fact that $T$ is a
tree. Hence, $|P|=1$, implying that $T$ is the path $P_{4}$. Therefore, if
$\mathcal{C}(T)=n$, then $T=P_{n}$ where $n\in[4]$. $\Box$

##  3 Trees with $\mathcal{C}(T)=n-1$

In this section, we characterize all trees $T$ with $\mathcal{C}(T)=n-1$.
Recall that for $r,s\geq 1$, a double star $S(r,s)$ is a tree with exactly two
(adjacent) vertices that are not leaves, with one of the vertices having $r$
leaf neighbors and the other $s$ leaf neighbors. We shall prove the following
result.

###### Theorem 8

If $T$ is a tree of order $n$, then $\mathcal{C}(T)=n-1$ if and only if
$T\in\\{K_{1,3},P_{5},P_{6},S(2,1)\\}$.

Proof.  Let $T$ be a tree of order $n$. If
$T\in\\{K_{1,3},P_{5},P_{6},S(2,1)\\}$, then it is straightforward to check
that $\mathcal{C}(T)=n-1$. To prove the necessity, suppose that
$\mathcal{C}(T)=n-1$. By Theorem 7, $\mathcal{C}(T)\leq n-1$ if and only if
$T=K_{1,3}$ or the order of $T$ is at least $5$. If $T$ contains a full
vertex, then $T$ is a star $K_{1,n-1}$ and $\mathcal{C}(T)=3$. By supposition,
$\mathcal{C}(T)=n-1$, implying that in this case, $T=K_{1,3}$ as desired.
Hence, we may assume that $T$ does not contain a full vertex, implying that
$n\geq 5$.

Let $\Psi$ be a $\mathcal{C}$-partition of $G$, and so $|\Psi|=n-1$ and $\Psi$
is a $c$-partition of $G$. Thus, each member of $\Psi$ is a singleton set of
cardinality $1$, except for one member in $\Psi$ of cardinality $2$. Let
$\Psi=\\{V_{1},\ldots,V_{n-1},U\\}$ where $|V_{i}|=1$ for $i\in[n-1]$ and
$|U|=2$. Let $x$ be a leaf of $T$ and let $y$ be the unique neighbor of $x$.
We proceed further with the following series of structural properties of the
tree $T$.

###### Claim 1

$U\neq\\{x,y\\}$.

Proof. Suppose, to the contrary, that $U=\\{x,y\\}$. Let $v\in V(T)\setminus
U$, and so $\\{v\\}\in\Psi$. If $\\{v^{\prime}\\}$ is a coalition partner of
$\\{v\\}$ for some $v^{\prime}\in V(T)\setminus U$, then the vertex $x$ is not
dominated by the set $\\{v,v^{\prime}\\}$, a contradiction. Hence, the
coalition partner of $\\{v\\}$ is the set $U$. In particular, $\\{v,y\\}$ is a
dominating set for all $v\in V(T)\setminus U$. Let $A$ be the set of vertices
in $V(T)\setminus U$ that are not adjacent to the vertex $y$, and let $B$ be
the set of vertices in $V(T)\setminus U$ that are dominated by $y$. If
$A=\emptyset$, then $y$ would be a full vertex, a contradiction. Hence,
$A\neq\emptyset$. As observed earlier, if $a\in A$, then $\\{a\\}$ and
$\\{x,y\\}$ form a coalition, implying that the vertex $a$ is adjacent to
every other vertex of $A$. Since this is true for all vertices $a\in A$, we
infer that $A$ is a clique. If $B=\emptyset$, then $T$ would be disconnected,
a contradiction. Hence, $B\neq\emptyset$. If $b\in B$, then $\\{b\\}$ and
$\\{x,y\\}$ form a coalition, implying that the vertex $b$ is adjacent to
every vertex of $A$. Since this is true for all vertices $b\in B$, every
vertex in $A$ is adjacent to every vertex in $B$. Hence, $\\{a,x\\}$ is a
dominating set for every vertex $a\in A$, and $\\{b,y\\}$ is a dominating set
for every vertex $b\in B$, implying that $\mathcal{C}(T)=n$, a contradiction.
($\Box$)

By Claim 1, $U\neq\\{x,y\\}$, and so $|U\cap\\{x,y\\}|\leq 1$. Since $T$ has
no full vertex, no vertex dominates $T$. Let $w$ be a vertex that is not
dominated by $y$. Let $N(w)=\\{w_{1},\ldots,w_{k}\\}$, and so $\deg_{G}(w)=k$
and $N(w)\cap\\{x,y\\}=\emptyset$. If two neighbors of $w$ are adjacent, then
these two vertices together with $w$ induce a triangle in $T$, a
contradiction. Hence since $T$ is a tree, the set $N(w)$ is an independent
set. If the vertex $y$ is adjacent to two vertices in $N(w)$, then these two
vertices together with $y$ and $w$ induce a $4$-cycle in $T$, a contradiction.
Hence the vertex $y$ is adjacent to at most one vertex in $N(w)$.

###### Claim 2

If $U\subseteq N(w)$, then $T=P_{5}$.

Proof. Suppose that $U\subseteq N(w)$, and so $U\cap\\{x,y\\}=\emptyset$.
Renaming vertices if necessary, we may assume that $U=\\{w_{1},w_{2}\\}$.
Suppose that $k\geq 3$. If $U$ forms a coalition with the set $\\{x\\}$, then
$U$ dominates the set $N(w)$, contradicting our earlier observation that the
set $N(w)$ is an independent set. Hence, $U$ does not form a coalition with
$\\{x\\}$, implying that $U$ forms a coalition with the set $\\{y\\}$. Thus,
$\\{y,w_{1},w_{2}\\}$ is a dominating set in $G$. Since $N(w)$ is an
independent set, the vertex $y$ therefore dominates the set
$N(w)\setminus\\{w_{1},w_{2}\\}$. Thus, $y$ is adjacent to at least $k-2$
vertices in $N(w)$. As observed earlier, $y$ is adjacent to at most one vertex
in $N(w)$. Therefore, $k=3$ and $y$ is adjacent to exactly one vertex in
$N(w)$, namely to the vertex $w_{3}$. Since $\\{x,w_{3}\\}$ does not dominate
the set $U$, the pair $\\{x\\}$ and $\\{w_{3}\\}$ do not form a coalition.
Since $\\{y,w_{3}\\}$ does not dominate the set $U$, the pair $\\{y\\}$ and
$\\{w_{3}\\}$ do not form a coalition. However, then the set
$\\{w_{3}\\}\in\Psi$ does not form a coalition with any other set in $\Psi$, a
contradiction. Hence, $k=2$, that is, $U=N(w)=\\{w_{1},w_{2}\\}$.

Suppose that $n\geq 6$. Let $z\in V(T)\setminus\\{x,y,w,w_{1},w_{2}\\}$. By
our earlier observations, $\\{z\\}$ forms a coalition with $\\{x\\}$ or with
$\\{y\\}$. Thus $\\{x,z\\}$ or $\\{y,z\\}$ is a dominating set of $G$. However
neither $y$ nor $z$ belong to $N(w)$, and so $\\{x,y,z\\}$ is not a dominating
set of $G$, a contradiction. Hence, $n=5$, that is,
$V(T)=\\{x,y,w,w_{1},w_{2}\\}$. Since $T$ is connected, the vertex $y$ is
adjacent to at least one of $w_{1}$ and $w_{2}$. However as observed earlier,
the vertex $y$ is adjacent to at most one of $w_{1}$ and $w_{2}$.
Consequently, the vertex $y$ is adjacent to exactly one of $w_{1}$ and
$w_{2}$, implying that $T$ is a path $P_{5}$. ($\Box$)

###### Claim 3

If $U\subseteq N[w]$, then $T=P_{5}$.

Proof. Suppose that $U\subseteq N[w]$, and so $U\cap\\{x,y\\}=\emptyset$. By
Claim 2, if $U\subseteq N(w)$, the $T=P_{5}$ as desired. Hence renaming
vertices if necessary, we may assume that $U=\\{w,w_{1}\\}$. Recall that
$n\geq 5$. Let $z\in V(T)\setminus\\{x,y,w,w_{1}\\}$. Thus, $\\{z\\}$ forms a
coalition with $\\{x\\}$ or with $\\{y\\}$. Thus $\\{x,z\\}$ or $\\{y,z\\}$ is
a dominating set of $G$. Since $y$ is not adjacent with $w$, the vertex
$y\notin N[w]$, and therefore the vertex $z$ is necessary adjacent to $w$.
Since $z$ is an arbitrary vertex in $V(T)\setminus\\{x,y,w,w_{1}\\}$, we have
that $V(T)=\\{x,y\\}\cup N[w]$. We now consider the vertex $w_{2}$. If
$\\{w_{2}\\}$ forms a coalition with $\\{x\\}$, then $\\{x,w_{2}\\}$ is a
dominating set, implying that $w_{1}$ and $w_{2}$ are adjacent, contradicting
our earlier observation that $N(w)$ is an independent set. Hence,
$\\{w_{2}\\}$ forms a coalition with $\\{y\\}$, then $\\{y,w_{2}\\}$ is a
dominating set, implying that $y$ and $w_{1}$ are adjacent. If $k\geq 3$, then
the vertex $w_{3}$ is not dominated by $\\{y,w_{2}\\}$, a contradiction.
Hence, $k=2$, and so $T$ is a path $P_{5}$. ($\Box$)

By Claim 3, we may assume that $|U\cap N[w]|\leq 1$, for otherwise $T=P_{5}$
and the desired result follow. By our earlier assumptions,
$|U\cap\\{x,y\\}|\leq 1$.

###### Claim 4

If $y\in U$, then $T\in\\{P_{5},S(2,1)\\}$.

Proof. Suppose that $y\in U$, and so $x\notin U$. Let $U=\\{y,z\\}$. By
definition of a coalition partition, the set $U$ is not a dominating set of
$G$ since the only sets $S\in\Psi$ that dominate $G$ have cardinality $|S|=1$.
Recall that $w$ was chosen earlier as an arbitrary vertex that is not adjacent
to $y$. Renaming vertices if necessary, we can choose $w$ to be a vertex not
dominated by the set $U$. Thus, $\\{x,y,z\\}\cap N[w]=\emptyset$. Recall that
$N(w)=\\{w_{1},\ldots,w_{k}\\}$. By our earlier observations, the set $N(w)$
is an independent set. Further since there is no $4$-cycle in $T$, every
vertex in $V(T)\setminus N[w]$ is adjacent to at most one vertex in $N(w)$.

Since the set $\\{x,y,z\\}$ is not a dominating set of $T$, the sets
$\\{x\\}\in\Psi$ and $U\in\Psi$ do not form a coalition. Hence, the set
$\\{x\\}\in\Psi$ forms a coalition with a set $\\{x^{\prime}\\}\in\Psi$, where
$x^{\prime}\notin\\{x,y,z\\}$. Since $\\{x,x^{\prime}\\}$ is a dominating set
of $T$, necessarily $x^{\prime}\in N[w]$. Since the vertex $z$ is not
dominated by the set $\\{x,w\\}$, we note that $x^{\prime}\neq w$, implying
that $x^{\prime}\in N(w)$. Renaming vertices if necessary, we may assume that
$x^{\prime}=w_{1}$. Thus, $\\{x,w_{1}\\}$ is a dominating set of $G$. Since
$N(w)$ is an independent set, this in turn implies that $k=|N(w)|=1$ and that
$w_{1}$ is adjacent to the vertex $z$. Suppose that $n\geq 6$, and so there
exists a vertex $q\in V(T)\setminus\\{x,y,w,w_{1},z\\}$. Since $\\{x,q\\}$ is
not a dominating set of $T$, the set $\\{q\\}\in\Psi$ does not form a
coalition with $\\{x\\}$, implying that the set $\\{q\\}\in\Psi$ forms a
coalition with the set $U\in\Psi$. However, the vertex $w$ is not dominated by
the set $\\{q,y,z\\}$, a contradiction. Hence, $n=5$, and so
$V(T)=\\{x,y,w,w_{1},z\\}$. As observed earlier,
$\\{xy,zw_{1},ww_{1}\\}\subset E(T)$. Since $T$ is connected, the only
remaining edge of $T$ is either $yw_{1}$ or $yz$. If $yw_{1}\in E(T)$, then
$T=S(2,1)$, while if $yz\in E(T)$, then $T=P_{5}$. ($\Box$)

By Claim 4, we may assume that $y\notin U$, for otherwise the desired result
follows.

###### Claim 5

If $x\notin U$, then $T\in\\{P_{5},S(2,1)\\}$.

Proof. Suppose that $x\notin U$. By assumption, $y\notin U$. Hence,
$\\{x\\}\in\Psi$ and $\\{y\\}\in\Psi$. Since $T$ has no full vertices, the
pair $\\{x\\}$ and $\\{y\\}$ do not form a coalition. By our earlier
assumptions, $|U\cap N[w]|\leq 1$. Let $U=\\{z_{1},z_{2}\\}$ and let $z_{1}\in
U\setminus N[w]$. By supposition, $U\cap\\{x,y\\}=\emptyset$, and so
$z_{1}\notin\\{x,y\\}$. Since $U$ forms a coalition with $\\{x\\}$ or
$\\{y\\}$, the set $\\{x,y,z_{1},z_{2}\\}$ is a dominating set of $T$,
implying that $z_{2}\in N[w]$ in order to dominate the vertex $w$.

Suppose that there is a vertex $z\in V(T)\setminus\left(\\{x,y,z_{1}\\}\cup
N[w]\right)$. Since $z\notin U$, $\\{z\\}\in\Psi$. By our earlier
observations, the pair $\\{z\\}$ and $\\{x\\}$ form a coalition or the pair
$\\{z\\}$ and $\\{y\\}$ form a coalition. However, the set $\\{x,y,z\\}$ does
not dominate the vertex $w$, and so $\\{z\\}$ does not form a coalition with
$\\{x\\}$ or with $\\{y\\}$, a contradiction. Hence, $V(T)=\\{x,y,z_{1}\\}\cup
N[w]$.

Suppose that $k\geq 2$. Renaming vertices in $N(w)$ if necessary, we may
assume that $w_{1}\neq z_{2}$, that is, $w_{1}\notin U$. Thus,
$\\{w_{1}\\}\in\Psi$. Since $\\{x,w_{1}\\}$ is not a dominating set of $T$
noting that $N(w)$ is an independent set of cardinality $k\geq 2$, the pair
$\\{w_{1}\\}$ and $\\{x\\}$ do not form a coalition, implying that the pair
$\\{w_{1}\\}$ and $\\{y\\}$ form a coalition. Thus, the vertex $y$ dominates
the set $N(w)\setminus\\{w_{1}\\}$. Since $y$ is adjacent to at most one
vertex in $N(w)$, we infer that $k=2$, $yw_{2}\in E(T)$, and $yw_{1}\notin
E(T)$. Analogously, if $w_{2}\neq z_{2}$, then $yw_{1}\in E(T)$ and
$yw_{2}\notin E(T)$, a contradiction. Hence, $w_{2}=z_{2}$. Thus,
$\\{w\\}\in\Psi$. Since $\\{x,w\\}$ does not dominate the vertex $z_{1}$, the
pair $\\{w\\}$ and $\\{x\\}$ do not form a coalition, implying that the pair
$\\{w\\}$ and $\\{y\\}$ form a coalition. This in turn implies that $yz_{1}\in
E(T)$. The tree is now determined and
$E(T)=\\{xy,yz_{1},yw_{2},w_{2}w,ww_{1}\\}$. Further,
$\Psi=\\{\\{x\\},\\{y\\},\\{w\\},\\{w_{1}\\},\\{z_{1},w_{2}\\}\\}$. However,
$\\{x\\}$ does not form a coalition with any other set in $\Psi$, a
contradiction.

Hence, $k=1$, and so $V(T)=\\{x,y,w,w_{1},z_{1}\\}$ and
$\\{xy,ww_{1}\\}\subset E(T)$. Since $T$ is a tree, exactly two of the edges
in the set $\\{yw_{1},yz_{1},w_{1}z_{1}\\}$ are present in $T$. If
$\\{yw_{1},yz_{1}\\}\subset E(T)$ or $\\{yw_{1},w_{1}z_{1}\\}\subset E(T)$,
then $T=S(2,1)$. If $\\{yz_{1},w_{1}z_{1}\\}\subset E(T)$, then $T=P_{5}$.
($\Box$)

By Claim 5, we may assume that $x\in U$, for otherwise the desired result
follows. Since $x$ is an arbitrary vertex of degree $1$ in $T$, we may
therefore assume that the set $U$ contains all vertices of degree $1$ in $T$.
Since $|U|=2$, this implies that $T$ is a path $P_{n}$ where $n\geq 5$. By
Theorem 2(a), $C(P_{n})=n-1$ if $n\in\\{5,6\\}$ and $C(P_{n})\leq n-2$ if
$n\geq 7$. Hence since $T=P_{n}$ and $\mathcal{C}(T)=n-1$, we infer that
$T\in\\{P_{5},P_{6}\\}$. This completes the proof of Theorem 8. $\Box$

As a consequence of Theorem 8, we have the following result.

###### Corollary 3

If $T$ is a tree of order $n$ with $n\geq 7$, then $\mathcal{C}(T)\leq n-2$.

##  4 Coalition graphs

In this section, we solve Problem 2 and Problem 3. In particular, we determine
the number of the coalition graphs that can be defined by all coalition
partitions of the path $P_{k}$ for a given positive integer $k$ (see Theorem
10) and then as a consequence of Theorem 10, we see that there is no universal
coalition path.

A coalition graph corresponding to a coalition partition of a path is called a
CP-_graph_ in [2]. We say a path $P_{k}$ defines a ${\rm CP}$-graph $G$ if
there is a coalition partition $\Psi$ of $P_{k}$ such that ${\rm
CG}(P_{k},\Psi)$ is isomorphic to $G$. In [2], Haynes et al. proved the
following theorem.

###### Theorem 9

([2]) A graph $G$ is a ${\rm CP}$-graph if and only if $G\in{\cal F}$.

According to Theorem 9, all 18 graphs of ${\cal F}$ are ${\rm CP}$-graph. For
$k\geq 2$, let the ordered list $s_{1},s_{2},\ldots,s_{k}$ be the vertices of
the path $P_{k}$ whose edges are $\\{s_{i},s_{i+1}\\}$ where $i\in[k-1]$. Now,
we prove the following proposition.

###### Proposition 3

The following properties hold.

  1. (a)

The path $P_{1}$ defines the ${\rm CP}$-graph $K_{1}$.

  2. (b)

The path $P_{2}$ defines the ${\rm CP}$-graph $\overline{K_{2}}$.

  3. (c)

The path $P_{3}$ defines the ${\rm CP}$-graph $K_{1}\cup K_{2}$.

  4. (d)

For any integer $k\geq 4$, the path $P_{k}$ does not define the ${\rm
CP}$-graphs $\overline{K_{2}}$ and $K_{1}\cup K_{2}$.

Proof.  It is immediate that the only path that defines the ${\rm CP}$-graph
$K_{1}$ is $P_{1}$. This establishes (a). For the path $P_{2}$, the set
$\left\\{\\{s_{1}\\},\\{s_{2}\\}\right\\}$ is a coalition partition and the
corresponding coalition graph is $\overline{K_{2}}$. This establishes (b). For
the path $P_{3}$, the set
$\left\\{\\{s_{1}\\},\\{s_{2}\\},\\{s_{3}\\}\right\\}$ is a coalition
partition such that none of the sets $\\{s_{1}\\}$ and $\\{s_{3}\\}$ is a
dominating set but they form a coalition. Moreover, the set $\\{s_{2}\\}$ is a
singleton dominating set. Hence, the coalition graph corresponding to
$\left\\{\\{s_{1}\\},\\{s_{2}\\},\\{s_{3}\\}\right\\}$ is $K_{1}\cup K_{2}$.
This establishes (c). Since the graphs $\overline{K_{2}}$ and $K_{1}\cup
K_{2}$ have at least one isolated vertex, their corresponding coalition
partition must contain at least one singleton dominating set. We know that for
any $k\geq 4$, the domination number of $P_{k}$ is at least two. Therefore,
every coalition partition of $P_{k}$ with $k\geq 4$ does not contain any
singleton dominating set. This proves part (d). $\Box$

By Proposition 1 and Theorem 2(a), we can readily deduce the following result.

###### Corollary 4

For any positive integer $k\leq 3$, the path $P_{k}$ does not define the ${\rm
CP}$-graphs $P_{3},K_{3},K_{1,3}$, $2K_{2}$,
$P_{4},C_{4},F_{1},K_{4}-e,P_{2}\cup P_{3},F_{2},B_{1},P_{5},S(2,1),S(2,2)$.

Next we prove several propositions about paths and their corresponding CP-
graphs.

###### Proposition 4

For $k\geq 4$, the path $P_{k}$ defines the ${\rm CP}$-graph $K_{2}$.

Proof.  For $k\geq 4$, let $\Psi=\\{A,B\\}$, where
$A=\\{s_{1},s_{2},\ldots,s_{\lfloor\frac{k}{2}\rfloor}\\}$ and
$B=\\{s_{\lfloor\frac{k}{2}\rfloor+1},\ldots,s_{k}\\}$. The sets $A$ and $B$
form a coalition, and so ${\rm CG}(P_{k},\Psi)\cong K_{2}$. $\Box$

###### Proposition 5

For $k\geq 4$, the path $P_{k}$ defines the ${\rm CP}$-graphs $P_{3}$ and
$C_{4}$.

Proof.  To prove the proposition, we provide two coalition partitions
$\Psi_{1}$ and $\Psi_{2}$ for $P_{k}$ with $k\geq 4$ whose corresponding
coalition graphs are $P_{3}$ and $C_{4}$, respectively. Let
$\Psi_{1}=\\{A,B,C\\}$, where

$A=\\{s_{1},s_{2}\\},\hskip
14.22636ptB=\bigcup_{i=2}^{\lceil\frac{k}{2}\rceil}\\{s_{2i-1}\\}\hskip
14.22636pt\mbox{and}\hskip
14.22636ptC=\bigcup_{i=2}^{\lfloor\frac{k}{2}\rfloor}\\{s_{2i}\\}.$

The sets $A$ and $B$ form a coalition, as do the sets $A$ and $C$. Moreover,
the sets $B$ and $C$ do not form a coalition. Hence, ${\rm
CG}(P_{k},\Psi_{1})\cong P_{3}$. Let $\Psi_{2}=\\{A,B,C,D\\}$, where

$A=\\{s_{1}\\},\hskip 14.22636ptB=\\{s_{2}\\},\hskip
14.22636ptC=\bigcup_{i=0}^{\lfloor\frac{k}{2}\rfloor-2}\\{s_{k-(2i+1)}\\}\hskip
14.22636pt\mbox{and}\hskip
14.22636ptD=\bigcup_{i=0}^{\lceil\frac{k}{2}\rceil-2}\\{s_{k-2i}\\}.$

The set $A$ forms a coalition with both sets $C$ and $D$, while the set $B$
forms a coalition with both sets $C$ and $D$. Moreover, the sets $A$ and $B$
do not form a coalition, and the sets $C$ and $D$ do not form a coalition.
Hence, ${\rm CG}(P_{k},\Psi_{2})\cong C_{4}$. $\Box$

###### Proposition 6

For $k\geq 5$, the path $P_{k}$ defines the ${\rm CP}$-graph $F_{1}$.

Proof.  Let $\Psi=\\{A,B,C,D\\}$ be the coalition partition of $P_{k}$ defined
as follows. For $k=6$, let $A=\\{s_{1},s_{5}\\}$, $B=\\{s_{3},s_{6}\\}$,
$C=\\{s_{4}\\}$ and $D=\\{s_{2}\\}$. For $k\geq 8$ even, let

$A=\left(\bigcup_{i=2}^{\frac{k}{2}-2}\\{s_{k-2i}\\}\right)\cup\\{s_{1},s_{k}\\},\hskip
14.22636ptB=\left(\bigcup_{i=2}^{\frac{k}{2}-2}\\{s_{k-(2i-1)}\\}\right)\cup\\{s_{2}\\},\hskip
14.22636ptC=\\{s_{k-2}\\}\hskip 14.22636pt\mbox{and}\hskip
14.22636ptD=\\{s_{3},s_{k-1}\\}.$

For $k\geq 5$ odd, let

$A=\left(\bigcup_{i=2}^{\frac{k-3}{2}}\\{s_{k-2i}\\}\right)\cup\\{s_{1},s_{k}\\},\hskip
14.22636ptB=\left(\bigcup_{i=2}^{\frac{k-3}{2}}\\{s_{k-(2i-1)}\\}\right)\cup\\{s_{2}\\},\hskip
14.22636ptC=\\{s_{k-2}\\}\hskip 14.22636pt\mbox{and}\hskip
14.22636ptD=\\{s_{k-1}\\}.$

The set $A$ forms a coalition with each of the sets $B$, $C$ and $D$, and the
sets $B$ and $D$ form a coalition. Moreover, the sets $B$ and $C$ do not form
a coalition, and the sets $C$ and $D$ do not form a coalition. Hence, ${\rm
CG}(P_{k},\Psi)\cong F_{1}$. $\Box$

###### Proposition 7

For $k\geq 6$, the path $P_{k}$ defines the ${\rm CP}$-graphs $K_{1,3}$,
$K_{3}$, $K_{4}-e$, and $P_{2}\cup P_{3}$.

Proof.  To prove the proposition, we provide four coalition partitions
$\Psi_{1},\Psi_{2},\Psi_{3}$ and $\Psi_{4}$ for $P_{k}$ with $k\geq 6$ whose
corresponding coalition graphs are $K_{1,3},K_{3},K_{4}-e$ and $P_{2}\cup
P_{3}$, respectively.

Let $\Psi_{1}=\\{A,B,C,D\\}$, where
$A=\\{s_{1},s_{2},\ldots,s_{k-4}\\}\cup\\{s_{k}\\}$, $B=\\{s_{k-3}\\}$,
$C=\\{s_{k-2}\\}$ and $D=\\{s_{k-1}\\}$. The set $A$ forms a coalition with
each of the sets $B$, $C$ and $D$. Moreover, there are no coalitions among the
sets $B$, $C$ and $D$. Hence, ${\rm CG}(P_{k},\Psi)\cong K_{1,3}$. Let
$\Psi_{2}=\\{A,B,C\\}$, where

$A=\left(\bigcup_{i=2}^{{\lfloor\frac{k}{3}\rfloor-1}}\\{s_{k-3i}\\}\right)\cup\\{s_{1},s_{k-2}\\},\hskip
14.22636ptB=\left(\bigcup_{i=1}^{\lfloor\frac{k}{3}\rfloor-1}\\{s_{k-(3i+1)}\\}\right)\cup\\{s_{2},s_{k}\\}\hskip
14.22636pt$

and

$C=\left(\bigcup_{i=1}^{{\lfloor\frac{k+1}{3}\rfloor-2}}\\{s_{k-(3i+2)}\\}\right)\cup\\{s_{k-1},s_{k-3}\\}.$

The set $A$ forms a coalition with each of the sets $B$ and $C$. Moreover, the
sets $B$ and $C$ form a coalition. Hence, ${\rm CG}(P_{k},\Psi_{2})\cong
K_{3}$. Let $\Psi_{3}=\\{A,B,C,D\\}$, where the coalition partition is defined
as follows. For $k\geq 6$ even, let $C=\\{s_{k-3}\\}$ and $D=\\{s_{k-2}\\}$,
and let

$A=\left(\bigcup_{i=0}^{\frac{k}{2}-3}\\{s_{2i+1}\\}\right)\cup\\{s_{k-1}\\}\hskip
7.11317pt\mbox{and}\hskip
7.11317ptB=\left(\bigcup_{i=1}^{\frac{k}{2}-2}\\{s_{2i}\\}\right)\cup\\{s_{k}\\}.$

For $k\geq 7$ odd, let $C=\\{s_{k-3}\\}$ and $D=\\{s_{k-2}\\}$, and let

$A=\left(\bigcup_{i=0}^{\frac{k-5}{2}}\\{s_{2i+1}\\}\right)\cup\\{s_{k}\\}\hskip
7.11317pt\mbox{and}\hskip
7.11317ptB=\left(\bigcup_{i=1}^{\frac{k-5}{2}}\\{s_{2i}\\}\right)\cup\\{s_{k-1}\\}.$

The set $A$ forms a coalition with each of the sets $B$, $C$ and $D$.
Moreover, the set $B$ forms a coalition with each of the sets $C$ and $D$.
However, the sets $C$ and $D$ do not form a coalition. Hence, ${\rm
CG}(P_{k},\Psi_{3})\cong K_{4}-e$. Let $\Psi_{4}=\\{A,B,C,D,F\\}$, where the
coalition partition is defined as follows. For $k\geq 6$ even, let
$B=\\{s_{2},s_{k-4}\\}$, $C=\\{s_{k-3}\\}$, and $D=\\{s_{k-2}\\}$ and let

$A=\left(\bigcup_{i=0}^{\frac{k-6}{2}}\\{s_{2i+1}\\}\right)\cup\\{s_{k}\\}\hskip
7.11317pt\mbox{and}\hskip
7.11317ptF=\left(\bigcup_{i=2}^{\frac{k-6}{2}}\\{s_{2i}\\}\right)\cup\\{s_{k-1}\\}.$

For $k\geq 7$ odd, let $B=\\{s_{2},s_{k-5}\\}$, $C=\\{s_{k-4}\\}$, and
$D=\\{s_{k-3}\\}$, and let

$A=\left(\bigcup_{i=0}^{\frac{k-7}{2}}\\{s_{2i+1}\\}\right)\cup\\{s_{k-1}\\}\hskip
7.11317pt\mbox{and}\hskip
7.11317ptF=\left(\bigcup_{i=2}^{\frac{k-7}{2}}\\{s_{2i}\\}\right)\cup\\{s_{k-2},s_{k}\\}.$

The sets $A$ and $C$, the sets $A$ and $D$, and the sets $B$ and $F$ are the
only pairs among the sets $A$, $B$, $C$, $D$, and $F$ in $\Psi_{4}$ that form
a coalition. Hence, ${\rm CG}(P_{k},\Psi_{4})\cong P_{2}\cup P_{3}$. $\Box$

###### Proposition 8

For $k\geq 7$, the path $P_{k}$ defines the ${\rm CP}$-graphs $P_{4}$ and
$P_{5}$.

Proof.  To prove the proposition, we provide two coalition partitions
$\Psi_{1}$ and $\Psi_{2}$ for $P_{k}$ with $k\geq 7$ whose corresponding
coalition graphs are $P_{4}$ and $P_{5}$, respectively. Let
$\Psi_{1}=\\{A,B,C,D\\}$, where $C=\\{s_{k-4}\\}$ and $D=\\{s_{k-1}\\}$, and
where

$A=\left(\bigcup_{i=3}^{\lceil\frac{k}{2}\rceil-2}\\{s_{k-2i}\\}\right)\cup\\{s_{1},s_{k-2},s_{k}\\}\hskip
7.11317pt\mbox{and}\hskip
7.11317ptB=\left(\bigcup_{i=3}^{\lfloor\frac{k}{2}\rfloor-1}\\{s_{k-(2i-1)}\\}\right)\cup\\{s_{2},s_{k-3}\\}.$

The sets $C$ and $A$, the sets $A$ and $B$, and the sets $B$ and $D$ are the
only pairs among the sets $A$, $B$, $C$, and $D$ in $\Psi_{1}$ that form a
coalition. Hence, ${\rm CG}(P_{k},\Psi_{1})\cong P_{4}$. Let
$\Psi_{2}=\\{A,B,C,D,F\\}$, where $C=\\{s_{3}\\}$, $D=\\{s_{4}\\}$, and
$F=\\{s_{5}\\}$, and where

$A=\left(\bigcup_{i=3}^{\lfloor\frac{k}{2}\rfloor}\\{s_{2i}\\}\right)\cup\\{s_{1}\\}\hskip
7.11317pt\mbox{and}\hskip
7.11317ptB=\left(\bigcup_{i=3}^{\lceil\frac{k}{2}\rceil-1}\\{s_{2i+1}\\}\right)\cup\\{s_{2}\\}.$

The sets $C$ and $A$, the sets $A$ and $D$, the sets $D$ and $B$, and the set
$B$ and $F$ are the only pairs among the sets $A$, $B$, $C$, $D$, and $F$ in
$\Psi_{2}$ that form a coalition. Hence, ${\rm CG}(P_{k},\Psi_{2})\cong
P_{5}$. $\Box$

###### Proposition 9

For $k\geq 8$, the path $P_{k}$ defines the ${\rm CP}$-graph $2K_{2}$.

Proof.  Let $\Psi=\\{A,B,C,D\\}$ be the coalition partition of $P_{k}$ defined
as follows.

For $k=8$, let $A=\\{s_{1},s_{7}\\}$, $B=\\{s_{2},s_{8}\\}$,
$C=\\{s_{3},s_{4}\\}$ and $D=\\{s_{5},s_{6}\\}$.

For $k=9$, let $A=\\{s_{1},s_{8}\\}$, $B=\\{s_{2},s_{4},s_{9}\\}$,
$C=\\{s_{3},s_{5}\\}$ and $D=\\{s_{6},s_{7}\\}$.

For $k=10$, let $A=\\{s_{1},s_{9}\\}$, $B=\\{s_{2},s_{4},s_{10}\\}$,
$C=\\{s_{3},s_{5},s_{6}\\}$ and $D=\\{s_{7},s_{8}\\}$.

For $k=11$, let $A=\\{s_{1},s_{10}\\}$, $B=\\{s_{2},s_{4},s_{11}\\}$,
$C=\\{s_{3},s_{5},s_{7}\\}$ and $D=\\{s_{6},s_{8},s_{9}\\}$.

For $k\geq 12$, let $A=\\{s_{1},s_{k-3},s_{k-1}\\}$ and
$B=\\{s_{2},s_{4},s_{k}\\}$, and let

$C=\left(\bigcup_{i=2}^{\lceil\frac{k}{2}\rceil-3}\\{s_{2i+1}\\}\right)\cup\\{s_{3}\\}\hskip
7.11317pt\mbox{and}\hskip
7.11317ptD=\left(\bigcup^{\lceil\frac{k}{2}\rceil-2}_{i=3}\\{s_{2i}\\}\right)\cup\\{s_{k-2}\\}.$

The sets $A$ and $C$, and the sets $B$ and $D$, are the only pairs among the
sets $A$, $B$, $C$, and $D$ in $\Psi$ that form a coalition. Hence, ${\rm
CG}(P_{k},\Psi)\cong 2K_{2}$. $\Box$

###### Proposition 10

For $k\geq 9$, the path $P_{k}$ defines the ${\rm CP}$-graphs $F_{2}$,
$B_{1}$, and $S(2,1)$.

Proof.  To prove the proposition, we provide three coalition partitions
$\Psi_{1},\Psi_{2}$ and $\Psi_{3}$ for $P_{k}$ with $k\geq 9$ whose
corresponding coalition graphs are $F_{2}$, $B_{1}$, and $S(2,1)$,
respectively. Let $\Psi_{1}=\\{A,B,C,D,F\\}$, where $C=\\{s_{3},s_{6}\\}$,
$D=\\{s_{4},s_{7}\\}$, and $F=\\{s_{5}\\}$, and where

$A=\left(\bigcup_{i=4}^{\lceil\frac{k}{2}\rceil-1}\\{s_{2i+1}\\}\right)\cup\\{s_{1}\\}\hskip
7.11317pt\mbox{and}\hskip
7.11317ptB=\left(\bigcup_{i=4}^{\lfloor\frac{k}{2}\rfloor}\\{s_{2i}\\}\right)\cup\\{s_{2}\\}.$

The set $A$ forms a coalition with each of the sets $C$ and $D$, and the set
$B$ forms a coalition with each of the sets $C$, $D$ and $F$. However, these
are the only pairs of sets in $\Psi_{1}$ that form a coalition, implying that
${\rm CG}(P_{k},\Psi_{1})\cong F_{2}$. Let $\Psi_{2}=\\{A,B,C,D,F\\}$, where
$C=\\{s_{3}\\}$, $D=\\{s_{5}\\}$, and $F=\\{s_{7}\\}$, and where

$A=\left(\bigcup_{i=4}^{\lfloor\frac{k}{2}\rfloor}\\{s_{2i}\\}\right)\cup\\{s_{1},s_{4}\\}\hskip
7.11317pt\mbox{and}\hskip
7.11317ptB=\left(\bigcup_{i=4}^{\lceil\frac{k}{2}\rceil-1}\\{s_{2i+1}\\}\right)\cup\\{s_{2},s_{6}\\}.$

The set $A$ forms a coalition with each of the sets $B$, $D$ and $F$, and the
set $B$ forms a coalition with each of the sets $A$, $C$ and $D$. However,
these are the only pairs of sets in $\Psi_{2}$ that form a coalition, implying
that ${\rm CG}(P_{k},\Psi_{2})\cong B_{1}$. Let $\Psi_{3}=\\{A,B,C,D,F\\}$,
where $C=\\{s_{3}\\}$, $D=\\{s_{4}\\}$, and $F=\\{s_{7}\\}$, and where

$A=\left(\bigcup_{i=3}^{\lfloor\frac{k}{2}\rfloor}\\{s_{2i}\\}\right)\cup\\{s_{1}\\}\hskip
7.11317pt\mbox{and}\hskip
7.11317ptB=\left(\bigcup_{i=4}^{\lceil\frac{k}{2}\rceil-1}\\{s_{2i+1}\\}\right)\cup\\{s_{2},s_{5}\\}.$

The set $A$ forms a coalition with each of the sets $B$, $C$ and $D$, and the
set $B$ forms a coalition with each of the sets $A$ and $F$. However, these
are the only pairs of sets in $\Psi_{2}$ that form a coalition, implying that
${\rm CG}(P_{k},\Psi_{2})\cong S(2,1)$. $\Box$

###### Proposition 11

For $k\geq 10$, the path $P_{k}$ defines the ${\rm CP}$-graph $S_{2,2}$.

Proof.  By Theorem 2(a), we have $C(P_{n})=6$ for all $k\geq 10$. Therefore,
there is a coalition partition of $P_{k}$ such that the corresponding ${\rm
CP}$-graph has six vertices. On the other hand, the only ${\rm CP}$-graph with
six vertices is $S_{2,2}$. Hence, the path $P_{k}$ with $k\geq 10$ defines the
${\rm CP}$-graph $S_{2,2}$. $\Box$

In Propositions 4–11, we presented results that determine which ${\rm
CP}$-graphs can be defined by the path $P_{k}$. But there are still cases that
have not yet been identified. For example, does $P_{8}$ define the ${\rm
CP}$-graphs $F_{2}$ and $B$ or does $P_{6}$ define the ${\rm CP}$-graphs
$2K_{2}$ and $P_{4}$? To this end, we empirically checked the remaining cases.
Table 1 summarizes the results of Corollary 4 and Propositions 3-11, and the
empirical results. In the table, we used the letters $Y,N,y$ and $n$. Let
$T(i,j)$ be the cell of the table in row $i$ and column $j$. Let ${\rm
CP}_{i}$ be the ${\rm CP}$-graph in row $i$, and let $P_{j}$ be the path in
column $j$. When $T(i,j)$ is equal to a uppercase letter, it means that using
Corollary 4 and Propositions 3-11, we have obtained the value of $T(i,j)$, and
when $T(i,j)$ is equal to a lowercase letter, it means that we empirically
have obtained it. If $T(i,j)\in\\{Y,y\\}$, it means that the ${\rm CP}$-graph
${\rm CP}_{i}$ can be defined by the path $P_{j}$, and if
$T(i,j)\in\\{N,n\\}$, it means that the ${\rm CP}$-graph ${\rm CP}_{i}$ cannot
be defined by the path $P_{j}$.

| $P_{1}$ | $P_{2}$ | $P_{3}$ | $P_{4}$ | $P_{5}$ | $P_{6}$ | $P_{7}$ | $P_{8}$ | $P_{9}$ | $P_{k\geq 10}$
---|---|---|---|---|---|---|---|---|---|---
$K_{1}$ | $Y$ | $N$ | $N$ | $N$ | $N$ | $N$ | $N$ | $N$ | $N$ | $N$
$K_{2}$ | $N$ | $n$ | $Y$ | $Y$ | $Y$ | $Y$ | $Y$ | $Y$ | $Y$ | $Y$
$\overline{K_{2}}$ | $N$ | $Y$ | $n$ | $N$ | $N$ | $N$ | $N$ | $N$ | $N$ | $N$
$K_{1}\cup K_{2}$ | $N$ | $N$ | $Y$ | $N$ | $N$ | $N$ | $N$ | $N$ | $N$ | $N$
$P_{3}$ | $N$ | $N$ | $N$ | $Y$ | $Y$ | $Y$ | $Y$ | $Y$ | $Y$ | $Y$
$K_{3}$ | $N$ | $N$ | $N$ | $n$ | $y$ | $Y$ | $Y$ | $Y$ | $Y$ | $Y$
$K_{1,3}$ | $N$ | $N$ | $N$ | $n$ | $n$ | $Y$ | $Y$ | $Y$ | $Y$ | $Y$
$2K_{2}$ | $N$ | $N$ | $N$ | $n$ | $n$ | $y$ | $y$ | $Y$ | $Y$ | $Y$
$P_{4}$ | $N$ | $N$ | $N$ | $n$ | $y$ | $y$ | $Y$ | $Y$ | $Y$ | $Y$
$C_{4}$ | $N$ | $N$ | $N$ | $Y$ | $Y$ | $Y$ | $Y$ | $Y$ | $Y$ | $Y$
$F_{1}$ | $N$ | $N$ | $N$ | $n$ | $Y$ | $Y$ | $Y$ | $Y$ | $Y$ | $Y$
$K_{4}-e$ | $N$ | $N$ | $N$ | $n$ | $n$ | $Y$ | $Y$ | $Y$ | $Y$ | $Y$
$P_{2}\cup P_{3}$ | $N$ | $N$ | $N$ | $n$ | $n$ | $Y$ | $Y$ | $Y$ | $Y$ | $Y$
$F_{2}$ | $N$ | $N$ | $N$ | $n$ | $n$ | $n$ | $n$ | $n$ | $Y$ | $Y$
$B$ | $N$ | $N$ | $N$ | $n$ | $n$ | $n$ | $n$ | $n$ | $Y$ | $Y$
$P_{5}$ | $N$ | $N$ | $N$ | $n$ | $n$ | $n$ | $Y$ | $Y$ | $Y$ | $Y$
$S(2,1)$ | $N$ | $N$ | $N$ | $n$ | $n$ | $n$ | $y$ | $y$ | $Y$ | $Y$
$S_{2,2}$ | $N$ | $N$ | $N$ | $n$ | $n$ | $n$ | $n$ | $n$ | $n$ | $Y$
Table 1: The ${\rm CP}$-graphs that can be defined by any path $P_{k}$ with
$k\geq 1$.

In the following, for the cases that $T(i,j)=y$, we present a coalition
partition of the path $P_{j}$ corresponding to the ${\rm CP}$-graph ${\rm
CP}_{i}$.

  1. $\bullet$

The path $P_{8}$ and the ${\rm CP}$-graph $S(2,1)$:
$\\{\\{1,4\\},\\{2,6,8\\},\\{3\\},\\{5\\},\\{7\\}\\}$.

  2. $\bullet$

The path $P_{7}$ and the ${\rm CP}$-graph $S(2,1)$:
$\\{\\{1,4\\},\\{2,6\\},\\{3\\},\\{5\\},\\{7\\}\\}$.

  3. $\bullet$

The path $P_{7}$ and the ${\rm CP}$-graph $2K_{2}$:
$\\{\\{1,7\\},\\{2\\},\\{3,4\\},\\{5,6\\}\\}$.

  4. $\bullet$

The path $P_{6}$ and the ${\rm CP}$-graph $P_{4}$:
$\\{\\{1,4\\},\\{2\\},\\{3,5\\},\\{6\\}\\}$.

  5. $\bullet$

The path $P_{6}$ and the ${\rm CP}$-graph $2K_{2}$:
$\\{\\{1,6\\},\\{2\\},\\{3,4\\},\\{5\\}\\}$.

  6. $\bullet$

The path $P_{5}$ and the ${\rm CP}$-graph $P_{4}$:
$\\{\\{1\\},\\{2\\},\\{3,4\\},\\{5\\}\\}$.

  7. $\bullet$

The path $P_{5}$ and the ${\rm CP}$-graph $K_{3}$:
$\\{\\{1,5\\},\\{2\\},\\{3,4\\}\\}$.

Let ${\rm NC}(P_{i})$ be the number of ${\rm CP}$-graphs that can be defined
by $P_{i}$. From Table 1, we can readily obtain the following result.

###### Theorem 10

It holds that ${\rm NC}(P_{1})={\rm NC}(P_{2})=1$, ${\rm NC}(P_{3})=2$, ${\rm
NC}(P_{4})=3$, ${\rm NC}(P_{5})=6$, ${\rm NC}(P_{6})=10$, ${\rm
NC}(P_{7})={\rm NC}(P_{8})=12$, ${\rm NC}(P_{9})=14$, and ${\rm NC}(P_{k})=15$
for any integer $k\geq 10$.

By Theorem 10, there is no path $P_{k}$ that defines all 18 ${\rm CP}$-graphs,
yielding the following result.

###### Theorem 11

There is no universal coalition path.

##  5 Conclusion

In this paper, we characterized all graphs $G$ of order $n$ with
$\delta(G)\leq 1$ and $\mathcal{C}(G)=n$. Furthermore, we characterized all
trees $T$ of order $n$ with $\mathcal{C}(T)=n$ and all trees $T$ of order $n$
with $\mathcal{C}(T)=n-1$. On the other hand, we theoretically and empirically
determined the number of coalition graphs that can be defined by all coalition
partitions of a given path $P_{k}$. Furthermore, we showed that there is no
universal coalition path. It remains an open problem to characterize all trees
$T$ of order $n$ with $\mathcal{C}(T)=n-k$ for all $k$ where $2\leq k\leq
n-2$. It would also be interesting to determine whether there is a linear-time
algorithm to compute the coalition number of a given tree.

## References

  * [1] T. W. Haynes, J. T. Hedetniemi, S. T. Hedetniemi, A. A. McRae, and R. Mohan, Introduction to coalitions in graphs. AKCE Int. J. Graphs Combin. 17 (2020) no. 2, 653–659.
  * [2] T. W. Haynes, J. T. Hedetniemi, S. T. Hedetniemi, A. A. McRae, and R. Mohan, Coalition graphs of paths, cycles and trees. Discuss. Math. Graph Theory (2020) DOI:https://doi.org/10.7151/dmgt.2416.
  * [3] T. W. Haynes, J. T. Hedetniemi, S. T. Hedetniemi, A. A. McRae, and R. Mohan, Upper bounds on the coalition number. Australas. J Comb. 80 (2021), no. 3, 442–453.
  * [4] T. W. Haynes, J. T. Hedetniemi, S. T. Hedetniemi, A. A. McRae, and R. Mohan, Coalition graphs. To appear in Commun. Comb. Optim. doi 10.22049/CCO.2022.27916.1394
  * [5] T. W. Haynes, S. T. Hedetniemi, and M. A. Henning (eds), _Topics in Domination in Graphs_ , Dev. Math., vol 64. Springer, Cham. (2020).
  * [6] T. W. Haynes, S. T. Hedetniemi, and M. A. Henning (eds), _Structures of Domination in Graphs_ , Dev. Math., vol 66. Springer, Cham. (2021).
  * [7] M. A. Henning and A. Yeo, _Total domination in graphs._ _Springer Monographs in Mathematics_. Springer, New York, 2013. xiv+178 pp. ISBN: 978-1-4614-6524-9.