Note on the Coalition Number of the dth Power of the n-Path

Qinglin Jia¹, Wenwei Zhao², Zhengyuan Jiang³, Yongqiang Zhao^1*

¹School of Mathematics and Physics, Hebei GEO University, Shijiazhuang, China.
²Department of Electrical Engineering, University of South Florida, Tampa, USA.
³Computer Science and Engineering Department, University of South Florida, Tampa, USA.

DOI: 10.4236/ojdm.2025.152002                

Abstract

In a graph $G=\left(V,E\right)$ , two disjoint sets $V_1,V_2\subseteq V$ are said to form a coalition, if neither $V_1$ nor $V_2$ is a dominating set of $G$ , but $V_1\cup V_2$ is a dominating set of $G$ . The sets $V_1$ and $V_2$ forming a coalition are said to be coalition partners. A coalition partition, called a c-partition, is a vertex partition $\pi =\left\{V_1,V_2,\cdots ,V_k\right\}$ such that each $V_i\in \pi$ satisfies the following conditions: $V_i$ is a singleton dominating set of $G$ , or $V_i$ is not a dominating set of $G$ but has a coalition partner $V_j\in \pi$ , a non-dominating set of $G$ . The maximum order $k$ of a c-partition of $G$ is called the coalition number, denoted by $C\left(G\right)$ . In this paper, we study the coalition numbers of the dth power of the n-path $P_n^d$ , get the exact values of $C\left(P_n^d\right)$ for enough large $n$ , and also provide some bounds of $C\left(P_n^d\right)$ for the other cases. As a special case, we get the exact values of $C\left(P_n^2\right)$ except for $n\in \left\{11,12,\cdots ,20\right\}$ .

Keywords

Coalition, Coalition Partition, Coalition Number, Dominating Set

1. Introduction

In this paper, all graphs are finite simple graphs. For a graph $G=\left(V,E\right)$ having vertex set $V$ and edge set $E$ , the open neighborhood and the closed neighborhood of a vertex $v\in V$ are denoted by $N\left(v\right)=\left\{u|uv\in E\right\}$ and $N\left[v\right]=N\left(v\right)\cup \left\{v\right\}$ , respectively. The degree of a vertex $v\in V$ , denoted by $d_G\left(v\right)$ , is the number of vertices in $N\left(v\right)$ . A full vertex of a graph $G$ is the vertex of degree $\left|V\right|-1$ , and an isolate vertex is the vertex of degree 0. The minimum degree and the maximum degree of $G$ are denoted by $\delta \left(G\right)$ and $\text{Δ}\left(G\right)$ , respectively. For a set $S\subseteq V$ , its open neighborhood is the set $N\left(S\right)={\displaystyle {\cup }_{v\in S}N\left(v\right)}$ , and its closed neighborhood is the set $N\left[S\right]=N\left(S\right)\cup S$ . Let $V^{\prime }$ be a nonempty subset of $V$ . If $\left|V^{\prime }\right|=1$ , then we call it a singleton set. Otherwise, we call it a non-singleton set. A dominating set $D\subseteq V$ of a graph $G$ is the set such that $N\left(x\right)\cap D\ne \varnothing$ for every vertex $x\in V-D$ . For two positive integers $a$ and $b$ with $a\le b$ , we denote the integer set $\left\{a,\cdots ,b\right\}$ by $\left[a,b\right]$ . Note that $\left[a,b\right]=\varnothing$ for $a>b$ . We denote the set of all even and odd numbers in $\left[a,b\right]$ by $\diamond \left[a,b\right]$ and $\circ \left[a,b\right]$ , respectively.

Coalitions and coalition partitions were first introduced by Haynes et al. [1] in 2020. In a graph $G$ , two disjoint sets $V_1,V_2\subseteq V$ are said to form a coalition, if neither $V_1$ nor $V_2$ is a dominating set of $G$ , but $V_1\cup V_2$ is a dominating set of $G$ . The sets $V_1$ and $V_2$ forming a coalition are said to be coalition partners. In a graph $G$ , a coalition partition called a c-partition, is a vertex partition $\pi =\left\{V_1,V_2,\cdots ,V_k\right\}$ such that each $V_i\in \pi$ satisfies the following conditions: $V_i$ is a singleton dominating set of $G$ , or $V_i$ is not a dominating set of $G$ but has a coalition partner $V_j\in \pi$ , a non-dominating set of $G$ . The maximum order $k$ of a c-partition of $G$ is called the coalition number, denoted by $C\left(G\right)$ . The partition $\pi =\left\{\left\{v_1\right\},\left\{v_2\right\},\cdots ,\left\{v_n\right\}\right\}$ is called the singleton partition of a graph $G$ with vertex set $\left\{v_1,v_2,\cdots ,v_n\right\}$ .

Suppose that $\pi =\left\{V_1,V_2,\cdots ,V_k\right\}$ be a c-partition of a graph $G$ . The coalition graph $CG\left(G,\pi \right)$ of $G$ is the graph with vertex set $\left\{V_1,V_2,\cdots ,V_k\right\}$ , and two vertices $V_i$ and $V_j$ are adjacent in $CG\left(G,\pi \right)$ if and only if the sets $V_i$ and $V_j$ in $\pi$ are coalition partners. If a graph $G$ is isomorphic to its coalition graph $CG\left(G,{\pi }^{\prime }\right)$ in which ${\pi }^{\prime }$ is the singleton partition of $G$ , then $G$ is called a self-coalition graph.

In 2020, Haynes et al. [1] first introduced the concepts: coalition, coalition partition and coalition number of a graph $G$ , studied these properties, and provided some bounds about $C\left(G\right)$ . Moreover, they determined the exact values of $C\left(P_n\right)$ and $C\left(C_n\right)$ for $n\ge 3$ , where $P_n$ and $C_n$ denote the path and cycle with $n$ vertices, respectively. In 2021, Haynes et al. [2] proved that $C\left(G\right)\le {\left(\text{Δ}\left(G\right)+3\right)}^2/4$ for any graph $G$ . They also showed that $C\left(G\right)\le \left(\delta \left(G\right)+1\right)\left(\text{Δ}\left(G\right)-\delta \left(G\right)+2\right)$ for a no full vertices graph $G$ with $\delta \left(G\right)<\text{Δ}\left(G\right)/2$ . In 2023, Davood Bakhshesh et al. [3] characterized all graphs $G$ of order $n$ with $\delta \left(G\right)\le 1$ and $C\left(G\right)=n$ . Moreover, they characterized all trees $T$ of order $n$ with $C\left(T\right)=n-1$ . In 2024, Saeid Alikhani et al. [4] studied the coalition number of the cubic graphs and provided the exact value of the coalition number of the cubic graphs with at most 10 vertices. In the same year, Dobrynin and Golmohammadi [5] constructed an infinite family of cubic graphs satisfying $C\left(G\right)=9$ .

In 2023, Haynes et al. [6] first studied the coalition graph and showed that every graph is a coalition graph. Then they [7] studied and characterized self-coalition graphs. Shortly after, they [8] studied and characterized the coalition graphs of paths, cycles and trees. In the same year, Davood Bakhshesh et al. [3] determined the number of coalition graphs that can be defined by all coalition partitions of a given path. In 2024, Dobrynin and Golmohammadi [9] showed that $C_{15}$ is the shortest cycle having the maximum number of coalition graphs.

In this paper, we investigate the coalition number of the dth power of the n-path $P_n^d$ , where $d\ge 2$ and $n\ge 3$ . In section 2, we provide the exact values or bounds of the coalition numbers of $P_n^d$ . In section 3, we determine the exact values of the coalition numbers of $P_n^2$ except for $n\in \left[11,20\right]$ .

2. The dth Power of the n-Path $P_n^d$

The following two lemmas are useful in this section.

Lemma 1 (Haynes et al.) Let $\pi$ be a $C\left(G\right)$ -partition of a graph $G$ with maximum degree $\Delta \left(G\right)$ . If $X\in \pi$ , then $X$ can form a coalition with each of at most $\Delta \left(G\right)+1$ other sets in $\pi$ , respectively.

Lemma 2 (Haynes et al.) Suppose that $G$ is a graph with maximum degree $\Delta \left(G\right)$ , then we have

$C\left(G\right)\le \frac{{\left(\text{Δ}\left(G\right)+3\right)}^2}{4}.$

For any positive integers $d\ge 2$ and $n\ge 3$ , the dth power of the n-path $P_n^d$ has the vertex set

$V\left(P_n^d\right)=\left\{v_1,v_2,\cdots ,v_n\right\}$

and the edge set

$E\left(P_n^d\right)={\displaystyle \underset{1\le i\le n-1}{\cup }\left\{v_i{v}_j|j=\text{min}\left\{i+1,n\right\},\text{min}\left\{i+2,n\right\},\cdots ,\text{min}\left\{i+d,n\right\}\right\}}.$

It is obvious that, for $n\le d+1$ , $P_n^d\cong K_n$ and $C\left(P_n^d\right)=C\left(K_n\right)=n$ . It is not difficult to see that, if $n\in \left[d+2,2d+2\right]$ , then for each vertex $x\in V\left(P_n^d\right)$ , there exists another vertex $y\in V\left(P_n^d\right)$ , such that $\left\{x\right\}$ and $\left\{y\right\}$ form a coalition of $P_n^d$ . So the following result holds.

Proposition 3. For any $d\ge 2$ , if $n\in \left[3,2d+2\right]$ , then we have

$C\left(P_n^d\right)=n.$

When $n\ge 2d+3$ , $\text{Δ}\left(P_n^d\right)=2d$ . By Lemma 1, we have

$C\left(P_n^d\right)\le \frac{{\left(\text{Δ}\left(P_n^d\right)+3\right)}^2}{4}=\frac{{\left(2d+3\right)}^2}{4}=\frac{4d^2+12d+9}{4}.$

So the following result is obvious.

Proposition 4. For any $d\ge 2$ , if $n\ge 2d+3$ , then we have

$C\left(P_n^d\right)\le \text{min}\left\{n,d^2+3d+2\right\}.$

Furthermore, we show that the upper bound is sharp as $n$ is large enough.

Theorem 5. For any $d\ge 2$ , if $n\ge 2d^2+5d+3$ , then we have

$C\left(P_n^d\right)=d^2+3d+2.$

Proof. Suppose that $n\ge 2d^2+5d+3$ , where $d\ge 2$ . By Proposition 4, in order to show that $C\left(P_n^d\right)=d^2+3d+2$ , we just need to prove that $C\left(P_n^d\right)\ge d^2+3d+2$ . To this end, in the following, we label the vertices of the graph $P_n^d$ with integers $i\in \left[1,d^2+3d+2\right]$ , define the set $V_i$ to consist of all vertices labeled $i$ , and then show that $\pi =\left\{V_1,V_2,\cdots ,V_{d^2+3d+2}\right\}$ is a c-partition of $C_n^d$ . Let $S_i=\left\{v_{\left(i-1\right)d+i},v_{\left(i-1\right)d+i+1},\cdots ,v_{\text{min}\left\{id+i,n\right\}}\right\}$ , in which $i\in \left[1,\lceil \frac{n}{d+1}\rceil \right]$ . Define a labeling $\ell :V\left(P_n^d\right)\to \left[1,d^2+3d+2\right]$ of the vertices of the graph $P_n^d$ as follows. Let

$\ell \left(v_j\right)=\{\begin{array}{ll}{\ell }^{\prime }\left(v_j\right),\hfill & \text{if}{\ell }^{\prime }\left(v_j\right)\le d+1\text{for}{v}_j\in S_i,i\in o\left[1,2d+2\right];\hfill \\ {\ell }^{\prime }\left(v_j\right)-\left(d+1\right),\hfill & \text{if}{\ell }^{\prime }\left(v_j\right)\ge d+2\text{for}{v}_j\in S_i,i\in o\left[1,2d+2\right];\hfill \\ {\ell }^{\prime }\left(v_j\right),\hfill & \text{for}{v}_j\in S_i,i\in \diamond \left[1,2d+2\right];\hfill \\ {\ell }^{\prime }\left(v_j\right),\hfill & \text{for}{v}_j\in S_i,i\in \left[2d+3,\lceil \frac{n}{d+1}\rceil \right],\hfill \end{array}$

where

${\ell }^{\prime }\left(v_j\right)=\{\begin{array}{ll}j-\left(i-1\right)d-\frac{i-1}{2},\hfill & \text{for}{v}_j\in S_i,i\in o\left[1,2d+2\right];\hfill \\ j-\left(\frac{i}{2}-1\right)\left(d+1\right),\hfill & \text{for}{v}_j\in S_i,i\in \diamond \left[1,2d+2\right];\hfill \\ j-\left(i-1\right)d-\left(i-1\right),\hfill & \text{for}{v}_j\in S_i,i\in \left[2d+3,\lceil \frac{n}{d+1}\rceil \right].\hfill \end{array}$

It is easy to see that $\ell \left(v_j\right)\in \left[1,d+1\right]$ for any $v_j\in S_i$ , where $i\in o\left[1,2d+2\right]\cup \left[2d+3,\lceil \frac{n}{d+1}\rceil \right]$ , and $\ell \left(v_j\right)\in \left[\frac{i}{2}d+\left(\frac{i}{2}+1\right),\left(\frac{i}{2}+1\right)d+\left(\frac{i}{2}+1\right)\right]$ for any $v_j\in S_i$ , where $i\in \diamond \left[1,2d+2\right]$ . So we have $\ell \left(v_j\right)\in \left[1,d^2+3d+2\right]$ for each $j\in \left[1,n\right]$ . For any $k\in \left[1,d^2+3d+2\right]$ , let $V_k=\left\{v_j|\ell \left(v_j\right)=k,j\in \left[1,n\right]\right\}$ . Note that for each $k\in \left[1,d^2+3d+2\right]$ , $V_k$ is not a dominating set of $C_n^d$ , and it is not difficult to check that for each $i\in \left[1,d+1\right]$ , $V_i$ forms a coalition with $V_j$ , where $j\in \left[id+\left(i+1\right),\left(i+1\right)d+\left(i+1\right)\right]$ . So $\pi =\left\{V_1,V_2,\cdots ,V_{d^2+3d+2}\right\}$ is a c-partition of $C_n^d$ , and we have $C\left(P_n^d\right)\ge d^2+3d+2$ . The proof is complete.□

It is easy to see that the subset $\left\{V_1,V_2,\cdots ,V_{d^2+3d+1}\right\}$ of $\pi =\left\{V_1,V_2,\cdots ,V_{d^2+3d+2}\right\}$ , defined in the proof of Theorem 5, is a c-partition of $P_n^d$ for $n=2d^2+5d+2$ . So the following result is immediately.

Corollary 6. For any $d\ge 2$ , if $n=2d^2+5d+2$ , then we have

$C\left(P_n^d\right)\ge d^2+3d+1.$

Theorem 7. For any $d\ge 2$ and any $t\in \left[1,d\right]$ ,

(1) if $2td+3t\le n\le \left(2t+1\right)d+\left(2t+1\right)$ , then we have

$C\left(P_n^d\right)\ge n-\left(t-1\right)d-\left(2t-1\right);$

(2) if $\left(2t+1\right)d+\left(2t+2\right)\le n\le \left(2t+2\right)d+\left(3t+2\right)$ , then we have

$C\left(P_n^d\right)\ge \left(t+2\right)d+2.$

Proof. (1) Suppose that $2td+3t\le n\le \left(2t+1\right)d+\left(2t+1\right)$ , in which $d\ge 2$ and $t\in \left[1,d\right]$ . Let $S_i=\left\{v_{\left(i-1\right)d+i},v_{\left(i-1\right)d+i+1},\cdots ,v_{\text{min}\left\{id+i,n\right\}}\right\}$ , where $i\in \left[1,\lceil \frac{n}{d+1}\rceil \right]$ . Define a labeling $\ell :V\left(P_n^d\right)\to \left[1,n-\left(t-1\right)d-\left(2t-1\right)\right]$ of the vertices of the graph $P_n^d$ as follows. Let

$\ell \left(v_j\right)=\{\begin{array}{ll}{\ell }^{\prime }\left(v_j\right),\hfill & \text{if}{\ell }^{\prime }\left(v_j\right)\le d+1\text{for}{v}_j\in S_i,i\in o\left[1,2t\right];\hfill \\ {\ell }^{\prime }\left(v_j\right)-\left(d+1\right),\hfill & \text{if}{\ell }^{\prime }\left(v_j\right)\ge d+2\text{for}{v}_j\in S_i,i\in o\left[1,2t\right];\hfill \\ {\ell }^{\prime }\left(v_j\right),\hfill & \text{for}{v}_j\in S_i,i\in \diamond \left[1,2t\right];\hfill \\ {\ell }^{\prime }\left(v_j\right),\hfill & \text{for}{v}_j\in S_{2t+1},\hfill \end{array}$

where

${\ell }^{\prime }\left(v_j\right)=\{\begin{array}{ll}j-\left(i-1\right)d-\frac{i-1}{2},\hfill & \text{for}{v}_j\in S_i,i\in o\left[1,2t\right];\hfill \\ j-\left(\frac{i}{2}-1\right)\left(d+1\right),\hfill & \text{for}{v}_j\in S_i,i\in \diamond \left[1,2t\right];\hfill \\ j-\left(t-1\right)\left(d+1\right),\hfill & \text{for}{v}_j\in S_{2t+1},j\in \left[2td+2t+1,n-t\right];\hfill \\ j-\left(n-t\right),\hfill & \text{for}{v}_j\in S_{2t+1},j\in \left[n-t+1,n\right].\hfill \end{array}$

It is easy to see that $\ell \left(v_j\right)\in \left[1,d+1\right]$ for any $v_j\in S_i\cup \left\{v_{n-t+1},\cdots ,v_n\right\}$ , where $i\in o\left[1,2t\right]$ ; $\ell \left(v_j\right)\in \left[\frac{i}{2}d+\left(\frac{i}{2}+1\right),\left(\frac{i}{2}+1\right)d+\left(\frac{i}{2}+1\right)\right]$ for any $v_j\in S_i$ , where $i\in \diamond \left[1,2t\right]$ ; and $\ell \left(v_j\right)\in \left[\left(t+1\right)d+\left(t+2\right),n-\left(t-1\right)d-\left(2t-1\right)\right]$ for $j\in \left[2td+2t+1,n-t\right]$ . So we have $\ell \left(v_j\right)\in \left[1,n-\left(t-1\right)d-\left(2t-1\right)\right]$ for each $j\in \left[1,n\right]$ . For any $k\in \left[1,n-\left(t-1\right)d-\left(2t-1\right)\right]$ , let $V_k=\left\{v_j|\ell \left(v_j\right)=k,j\in \left[1,n\right]\right\}$ . Note that for each $k\in \left[1,n-\left(t-1\right)d-\left(2t-1\right)\right]$ , $V_k$ is not a dominating set of $C_n^d$ , and it is not difficult to check that for each $i\in \left[1,t\right]$ , $V_i$ forms a coalition with $V_j$ , where $j\in \left[id+\left(i+1\right),\left(i+1\right)d+\left(i+1\right)\right]$ . When $n=2td+3t$ , for each $i\in \left[t+1,n\right]$ , $V_i$ forms a coalition with $V_{\left(t+1\right)d+\left(t+1\right)}$ . When $n>2td+3t$ , for each $i\in \left[1,n-t-\left(2td+\left(2t+1\right)\right)\right]$ , $V_{t+i}$ forms a coalition with $V_{\left(t+1\right)d+\left(t+1\right)+i}$ ; for each $i\in \left[n-t-\left(2td+\left(2t+1\right)\right)+1,d+1\right]$ , $V_{t+i}$ forms a coalition with $V_{\left(t+1\right)d+\left(t+1\right)+\left(n-t-\left(2td+\left(2t+1\right)\right)+1\right)}$ , i.e., $V_{n-\left(t-1\right)d-\left(2t-1\right)}$ . So $\pi =\left\{V_1,V_2,\cdots ,V_{n-\left(t-1\right)d-\left(2t-1\right)}\right\}$ is a c-partition of $P_n^d$ , and we have $C\left(P_n^d\right)\ge n-\left(t-1\right)d-\left(2t-1\right)$ .

(2) Suppose that $\left(2t+1\right)d+\left(2t+2\right)\le n\le \left(2t+2\right)d+\left(3t+2\right)$ , where $d\ge 2$ and $t\in \left[1,d\right]$ . Let $S_i=\left\{v_{\left(i-1\right)d+i},v_{\left(i-1\right)d+i+1},\cdots ,v_{\text{min}\left\{id+i,n\right\}}\right\}$ , in which $i\in \left[1,\lceil \frac{n}{d+1}\rceil \right]$ . Define a labeling $\ell :V\left(P_n^d\right)\to \left[1,\left(t+2\right)d+2\right]$ of the vertices of the graph $P_n^d$ as follows. Let

$\ell \left(v_j\right)=\{\begin{array}{ll}{\ell }^{\prime }\left(v_j\right),\hfill & \text{if}{\ell }^{\prime }\left(v_j\right)\le d+1\text{for}{v}_j\in S_i,i\in o\left[1,2t\right];\hfill \\ {\ell }^{\prime }\left(v_j\right)-\left(d+1\right),\hfill & \text{if}{\ell }^{\prime }\left(v_j\right)\ge d+2\text{for}{v}_j\in S_i,i\in o\left[1,2t\right];\hfill \\ {\ell }^{\prime }\left(v_j\right),\hfill & \text{for}{v}_j\in S_i,i\in \diamond \left[1,2t\right],\hfill \end{array}$

where

${\ell }^{\prime }\left(v_j\right)=\{\begin{array}{ll}j-\left(i-1\right)d-\frac{i-1}{2},\hfill & \text{for}{v}_j\in S_i,i\in o\left[1,2t\right];\hfill \\ j-\left(\frac{i}{2}-1\right)\left(d+1\right),\hfill & \text{for}{v}_j\in S_i,i\in \diamond \left[1,2t\right],\hfill \end{array}$

and let

$\ell \left(v_j\right)=\{\begin{array}{ll}\ell \left(v_j\right)=j-\left(t-1\right)d-t+1,\hfill & \text{for}j\in T_1;\hfill \\ \ell \left(v_j\right)=j-\left(2t+1\right)d-t-1,\hfill & \text{for}j\in T_2;\hfill \\ \ell \left(v_j\right)=j-\left(2t+2\right)d-t-2,\hfill & \text{for}j\in T_3;\hfill \\ \ell \left(v_j\right)=j-\left(2t+3\right)d-t-3,\hfill & \text{for}j\in T_4,\hfill \end{array}$

in which

$T_1=\left[2td+2t+1,\left(2t+1\right)d+t+1\right]$ ,

$T_2=\left[\left(2t+1\right)d+t+2,\left\{\left(2t+2\right)d+t+2,n\right\}\right]$ ,

$T_3=\left[\left(2t+2\right)d+t+3,\left\{\left(2t+3\right)d+t+3,n\right\}\right]$ , and

$T_4=\left[\left(2t+3\right)d+t+4,n\right]$ .

It is easy to see that $\ell \left(v_j\right)\in \left[1,d+1\right]$ for any $v_j\in S_i\cup \left\{v_{\left(2t+1\right)d+t+2},\cdots ,v_n\right\}$ , where $i\in o\left[1,2t\right]$ ; $\ell \left(v_j\right)\in \left[\frac{i}{2}d+\left(\frac{i}{2}+1\right),\left(\frac{i}{2}+1\right)d+\left(\frac{i}{2}+1\right)\right]$ for any $v_j\in S_i$ , where $i\in \diamond \left[1,2t\right]$ ; and $\ell \left(v_j\right)\in \left[\left(t+1\right)d+t+2,\left(t+2\right)d+2\right]$ for any $v_j\in \left\{v_{2td+2t+1},\cdots ,v_{\left(2t+1\right)d+t+1}\right\}$ . So we have $\ell \left(v_j\right)\in \left[1,\left(t+2\right)d+2\right]$ for each $j\in \left[1,n\right]$ . For any $k\in \left[1,\left(t+2\right)d+2\right]$ , let $V_k=\left\{v_j|\ell \left(v_j\right)=k,j\in \left[1,n\right]\right\}$ . Note that for each $k\in \left[1,\left(t+2\right)d+2\right]$ , $V_k$ is not a dominating set of $C_n^d$ , and it is not difficult to check that for each $i\in \left[1,t\right]$ , $V_i$ forms a coalition with $V_j$ , where $j\in \left[id+\left(i+1\right),\left(i+1\right)d+\left(i+1\right)\right]$ ; for each $i\in \left[t+1,d+1\right]$ , $V_i$ forms a coalition with $V_{\left(t+1\right)d+\left(i+1\right)}$ . So $\pi =\left\{V_1,V_2,\cdots ,V_{\left(t+2\right)d+2}\right\}$ is a c-partition of $P_n^d$ , and we have $C\left(P_n^d\right)\ge \left(t+2\right)d+2$ .□

3. The Power of the n-Path $P_n^2$

By the results about $C\left(P_n^d\right)$ provided in previous section, as a special case for $d=2$ , The following results are obvious.

Corollary 8. For any $n\ge 3$ ,

(1) if $3\le n\le 6$ , then we have $C\left(P_n^2\right)=n$ ;

(2) if $7\le n\le 9$ , then we have $n-1\le C\left(P_n^2\right)\le n$ ;

(3) if $10\le n\le 12$ , then we have $8\le C\left(P_n^2\right)\le n$ ;

(4) if $13\le n\le 15$ , then we have $n-5\le C\left(P_n^2\right)\le 12$ ;

(5) if $16\le n\le 19$ , then we have $10\le C\left(P_n^2\right)\le 12$ ;

(6) if $n=20$ , then we have $11\le C\left(P_n^2\right)\le 12$ ;

(7) if $n\ge 21$ , then we have $C\left(P_n^2\right)=12$ .

In fact, some upper bounds can be further optimized. For convenience, we may assume that $\left|V_1|\ge |V_2\left|\ge \cdots \ge \right|V_k\right|$ for any c-partition $\pi =\left\{V_1,V_2,\cdots ,V_k\right\}$ of a graph $G$ .

Observation 9. It is not difficult to verify the following statements.

(1) If $n\ge 7$ , then $v_4$ can not form a dominating set with any other vertex of $P_n^2$ ;

(2) Except for $\left\{v_3,v_8\right\}$ , any two vertices of $P_{10}^2$ can not form a dominating set;

(3) If $n\ge 11$ , then any two vertices of $P_n^2$ can not form a dominating set.

Corollary 10. $C\left(P_n^2\right)=\{\begin{array}{ll}n-1,\hfill & \text{if}n\in \left[7,9\right]\hfill \\ 8,\hfill & \text{if}n=10\hfill \end{array}$ .

Proof. By (1) of Observation 9, we have $C\left(P_n^2\right)\le n-1$ for $n\ge 7$ . By (2) of Corollary 8, we have $C\left(P_n^2\right)=n-1$ for $n\in \left[7,9\right]$ . By (3) of Corollary 8, we have $8\le C\left(P_{10}^2\right)\le 9$ . Suppose that $C\left(P_{10}^2\right)=9$ and $\pi =\left\{V_1,V_2,\cdots ,V_9\right\}$ is a c-partition of $P_{10}^2$ . Then we just need to consider the case: $\left|V_1\right|=2$ and $\left|V_2|=|V_3\left|=\cdots =\right|V_9\right|=1$ . By Lemma 1, $V_1$ can form a coalition with each of at most 5 singleton sets in $\pi$ , respectively. Then in $\pi$ there are at least 3 other singleton sets. By (2) of Observation 9, at least 1 of these 3 singleton sets cannot form a coalition with any other set in $\pi$ , a contradiction. So we have $C\left(P_{10}^2\right)\le 8$ and $C\left(C_{10}^2\right)=8$ .□

For $n\in \left[11,20\right]$ , we conjecture that the lower bounds of $C\left(P_n^2\right)$ provided in Corollary 8 are the exact values of $C\left(P_n^2\right)$ . But the proof of this may be tedious.

For the further research, it would be interesting to study the coalition number of regular graphs and graphs with special structure.

Conflicts of Interest

The authors declare no conflicts of interest regarding the publication of this paper.

References

[1]	Haynes, T.W., Hedetniemi, J.T., Hedetniemi, S.T., McRae, A.A. and Mohan, R. (2020) Introduction to Coalitions in Graphs. AKCE International Journal of Graphs and Combinatorics, 17, 653-659. https://doi.org/10.1080/09728600.2020.1832874
[2]	Haynes, T.W., Hedetniemi, J.T., Hedetniemi, S.T., McRae, A.A. and Mohan, R. (2021) Upper Bounds on the Coalition Number. Australasian Journal of Combinatorics, 80, 442-453.
[3]	Bakhshesh, D., Henning, M.A. and Pradhan, D. (2023) On the Coalition Number of Trees. Bulletin of the Malaysian Mathematical Sciences Society, 46, Article No. 95. https://doi.org/10.1007/s40840-023-01492-4
[4]	Alikhani, S., Golmohammadi, H. and Konstantinova, E.V. (2024) Coalition of Cubic Graphs of Order at Most 10. Communications in Combinatorics and Optimization, 9, 437-450.
[5]	Dobrynin, A.A. and Golmohammadi, H. (2024) On Cubic Graphs Having the Maximum Coalition Number. Siberian Electronic Mathematical Reports-Sibirskie Elektronnye Matematicheskie Izvestiya, 21, 363-369.
[6]	Haynes, T.W., Hedetniemi, J.T., Hedetniemi, S.T., McRae, A.A. and Mohan, R. (2023) Coalition Graphs. Communications in Combinatorics and Optimization, 8, 423-430. http://doi.org/10.22049/CCO.2022.27916.1394
[7]	Haynes, T.W., Hedetniemi, J.T., Hedetniemi, S.T., McRae, A.A. and Mohan, R. (2023) Self-Coalition Graphs. Opuscula Mathematica, 43, 173-183. https://doi.org/10.7494/opmath.2023.43.2.173
[8]	Haynes, T., Hedetniemi, J., Hedetniemi, S.T., McRae, A. and Mohan, R. (2023) Coalition Graphs of Paths, Cycles, and Trees. Discussiones Mathematicae Graph Theory, 43, 931. https://doi.org/10.7151/dmgt.2416
[9]	Dobrynin, A.A. and Golmohammadi, H. (2024) The Shortest Cycle Having the Maximal Number of Coalition Graphs. Discrete Mathematics Letters, 14, 21-26.