For a graph \(G=(V,E)\), a pair of vertex disjoint sets \(A_{1}\) and \(A_{2}\) form a connected coalition of \(G\), if \(A_{1}\cup A_{2}\) is a connected dominating set, but neither \(A_{1}\) nor \(A_{2}\) is a connected dominating set. A connected coalition partition of \(G\) is a partition \(\Phi\) of \(V(G)\) such that each set in \(\Phi\) either consists of only a singe vertex with the degree \(\mid V(G)\mid-1\), or forms a connected coalition of \(G\) with another set in \(\Phi\). The connected coalition number of \(G\), denoted by \(CC(G)\), is the largest possible size of a connected coalition partition of \(G\). In this paper, we characterize graphs that satisfy \(CC(G)=2\). Moreover, we obtain the connected coalition number for unicycle graphs and for the corona product and join of two graphs. Finally, we give a lower bound on the connected coalition number of the Cartesian product and the lexicographic product of two graphs.
Let \(G\) be a graph. We denote by \(V(G)\) and \(E(G)\) the vertex set and edge set of \(G\), respectively, and call \(\mid V(G)\mid\) the order of \(G\). A neighbour of a vertex \(v\) is a vertex adjacent to \(v\). The degree of a vertex \(v\in V\), denoted by \(deg(v)\), is the number of its neighborhoods. A vertex with degree \(\mid V(G)\mid-1\) in a graph \(G\) is called a full vertex. A vertex \(v\) in \(G\) is referred to as a pendant vertex if \(deg(v)=1\). For a vertex subset \(S\subseteq V\), the subgraph induced by \(S\), denoted by \(G[S]\), is the subgraph whose vertex set is \(S\) and whose edge set consists of all edges of \(G\) which have both ends in \(S\). The subgraph \(G-S\) is the subgraph obtained by removing all vertices in \(S\) and removing all edges incident with some vertex in \(S\) from the graph \(G\).
Many questions in combinatorics can be described as a certain type of domination problems in graphs. There is a vast literature on the various domination, see for instance five fundamental books [8, 14, 15, 16, 18] and two surveys [9, 17]. In this paper, we study the connected coalition number of graphs, introduced recently by Alikhani, Bakhshesh, Golmohammadi and Konstantinova [1], similar to the coalition number. We only consider simple and finite graphs throughout this paper. Definitions which are not given here may be found in [6]. Cockayne and Hedetniemi [7] defined the domatic number of a graph. Later, the connected domatic number of a graph is introduced by Zelinka [21].
Definition 1.1. Let \(G\) be a graph. A vertex subset \(S\subseteq V(G)\) is called a dominating set of \(G\), if for each vertex \(v\in V(G)\backslash S\), there exists at least one vertex \(u\in S\) with \(uv\in E(G)\). A vertex subset \(S\) is called a connected dominating set of \(G\), if \(S\) is a dominating set and \(G[S]\) is connected. A connected domatic partition of \(G\) is a partition of \(V(G)\) into connected dominating sets. The connected domatic number of \(G\), denoted by \(d_{c}(G)\), is the maximum size of a connected domatic partition in \(G\).
We refer the readers to [10, 19, 20, 21] for more details and results on the domatic number and the connected domatic number of a graph. Haynes et al. [11] first introduced the concept of coalitions and coalition partitions in the field of graph theory. Later, the coalition number of some families of graphs is researched, see [3, 4, 12, 13]. In 2022, Alikhani et al. [2] introduced the concept of total coalitions of a graph. In 2023, Barát and Blázsik [5] obtained a general sharp upper bound on the total coalition number as a function of the maximum degree. Recently, Alikhani et al. [1] introduced the concept of connected coalitions and connected coalition partitions in a graph.
Definition 1.2. Let \(G\) be a graph. A pair of vertex disjoint sets \(A_{1}\) and \(A_{2}\) form a connected coalition of \(G\), if \(A_{1}\cup A_{2}\) is a connected dominating set, but neither \(A_{1}\) nor \(A_{2}\) is a connected dominating set. A partition \(\Phi=\{A_{1},A_{2},\ldots,A_{k}\}\) of \(V(G)\) is called a connected coalition partition of \(G\), if for each set \(A_{i}\in \Phi\), either \(A_{i}=\{v\}\) for some full vertex \(v\) of \(G\), or \(A_{i}\) and \(A_{j}\) form a connected coalition of \(G\) for another set \(A_{j}\in\Phi\). The connected coalition number of a graph \(G\), denoted by \(CC(G)\), is the maximum cardinality of a connected coalition partition in \(G\). For a connected coalition partition \(\Phi\) of \(G\), we say that \(\Phi\) is a \(CC(G)\)–partition if \(\mid\Phi\mid=CC(G)\).
Clearly, the connected coalition number of a graph is at most the number of vertices. This upper bound can be obtain for complete graphs and complete bipartite graphs \(K_{m,n}\) with \(2\leq m\leq n\). Alikhani et al. [1, Lemma 1] proved that \(CC(G)=1\) if and only if \(G=K_{1}\) for any graph \(G\). Note that if there is no connected coalition partition for a graph \(G\), then \(CC(G)=0\). Let \(\mathcal{F}\) be a family of graphs \(H\) satisfying that the subgraph obtained by removing all full vertices from \(H\) is not connected. Alikhani et al. [1, Lemma 10] obtained that \(CC(G)=0\) if and only if \(G\in \mathcal{F}\). Hence, the following statement also holds.
Theorem 1.3. [1, Lemma 6] If \(G\) is a connected graph of order \(n\geq 2\) with no full vertex, then \(CC(G)\geq 2\).
Alikhani et al. [1] also proved that \(CC(G)\geq 2d_{c}(G)\) for any connected graph \(G\) of order \(n\) with no full vertex, and provided two polynomial-time algorithm to find graphs \(G\) with \(CC(G)=n-1\) and \(CC(G)=n\). For a tree \(T\) with order \(n\), it is clear that if \(n=1\), then \(CC(T)=1\); if \(n=2\), then \(CC(T)=2\). Moveover, if \(n\geq 3\) and there is a full vertex in \(T\), then \(T\in \mathcal{F}\) and hence \(CC(T)=0\).
Theorem 1.4. [1, Lemma 17]] For any tree \(T\) with no full vertex, we have \(CC(T)=2\).
In this paper, we give a brief proof of Theorem 1.4 by proving the following result in Section 2.
Theorem 1.5. Let \(G\) be a connected graph with no full vertex. Let \(X=\{v\in V(G)\mid G-v\) is not connected \(\}\). Then \(CC(G)=2\) if and only if \(X\) is a connected dominating set of \(G\).
The corona product of two graphs \(G\) and \(H\), denoted by \(G\circ H\), is defined as the graph obtained by taking one copy of \(G\) and \(\mid V(G)\mid\) copies of \(H\) and joining the \(i\)-th vertex of \(G\) to every vertex of the \(i\)-th copy of \(H\). Alikhani et al. [1] determined the connected coalition number of \(G\circ K_{1}\) for any connected graph \(G\).
Theorem 1.6. [1, Lemma 15] \(CC(G\circ K_{1})=2\) for any connected graph \(G\).
Alikhani et al. [1] posed the following question.
Question 1.7. What is the connected coalition number of the corona product, the join, the Cartesian product and the lexicographical product of two graphs?
By Theorem 1.5, we obtain the connected coalition number of the corona product of two graphs, which generalizes Theorem 1.6.
Corollary 1.8. Let \(G\) be a connected graph. Then for any graph \(H\), we have \[CC(G\circ H)=\left\{\begin{array}{ll} 2, &\text{if $\mid V(G)\mid \geq 2$},\\ 0,&\text{if $\mid V(G)\mid =1$ and $CC(H)=0$},\\ 1+CC(H),&\text{if $\mid V(G)\mid=1$ and $CC(H)\neq 0$}. \end{array}\right.\]
The join of two graphs \(G\) and \(H\), denoted by \(G\vee H\), is defined as the graph formed by connecting every vertex of \(G\) and every vertex of \(H\) from disjoint copies \(G\) and \(H\).
Theorem 1.9. Let \(G\) and \(H\) be two graphs. Then \[CC(G\vee H)=\left\{\begin{array}{ll} \mid V(G)\mid+\mid V(H)\mid, &\text{if neither $G$ nor $H$ are complete graphs},\\ &\text{if one of $G$ and $H$ is a complete graph }\\ 0,& \text{and another has connected coalition}\\ &\text{number $0$},\\ CC(G)+CC(H),&\text{others}. \end{array}\right.\]
We study the connected coalition number of unicycle graphs in Section 3. A family \(\mathcal{G}\) of graphs is constructed as follows: the graphs obtained by identifying a vertex of \(K_{3}\) and the full vertex of star graphs, see Figure 1 (a).
Theorem 1.10. Let \(G\) be an unicycle graph of order \(n\) with the cycle \(C_{m}\), and let \(Y=\{v\in V(C_{m})\mid G-v \ \text{is connected~}\}\). Then \[CC(G)=\left\{\begin{array}{ll} 4, &\text{if $G=C_{4}$},\\ 0,&\text{if $G\in \mathcal{G}$},\\ 2, &\text{if $n\geq 5$ and $\mid Y \mid \leq 1$ or $G[Y]=K_{2}$},\\ 3,&\text{others}. \end{array}\right.\]
Further, in Section 4 of this paper, we provide a lower bound for the connected coalition number of the Cartesian product and the lexicographical product of two graphs.
In this section, we give proofs of Theorems 1.5 and 1.9. Moreover, we give a proof of Corollary 1.8 and provide a brief proof of Theorem 1.4 by using Theorem 1.5.
Let \(G\) be a graph of order \(n\) with \(CC(G)\geq 1\). If \(deg(v)=n-1\) for some vertex \(v\in V(G)\), then \(\{v\}\in \Phi\) for any \(CC(G)\)-partition \(\Phi\). We begin our proof with the following observation.
Observation 2.1. Let \(G\) be a connected graph with a full vertex \(v\), and let \(H=G-v\). Then \[CC(G)=\left\{\begin{array}{ll} 0,&\text{if $CC(H)=0$},\\ 1+CC(H),&\text{if $CC(H)\neq 0$}. \end{array}\right.\]
Now, we give a proof of Theorem 1.9 by Observation 2.1.
Proof of Theorem 1.9. Assume first that neither \(G\) nor \(H\) are complete graphs. Let \(\Phi\) be a partition of \(V(G\vee H)\) such that each vertex forms a set of \(\Phi\). Further, we take \[V_{1}(G)=\{v\in V(G)\mid v \ \text{is not a full vertex in}\ G\},\] and \[V_{1}(H)=\{v\in V(H)\mid v \ \text{is not a full vertex in}\ H\}.\]
Then \(V_{1}(G)\neq \emptyset\) and \(V_{1}(H)\neq \emptyset\). It is easy to see that \(\{v\}\) and \(\{w\}\) forms a connected coalition of \(G\vee H\) for any \(v\in V_{1}(G)\) and \(w\in V_{1}(H)\). Note that \(u\) is a full vertex in \(G\vee H\) for all \(u\in V(G\vee H)\backslash (V_{1}(G)\cup V_{1}(H))\). This implies that \(\Phi\) is a connected coalition partition of \(G\vee H\). Therefore, \(CC(G\vee H)=\mid V(G)\mid+\mid V(H)\mid\).
Further, assume that there is at least one complete graph in \(G\) and \(H\). Recall that the connected coalition number of a complete graph is the number of its vertex set. Therefore, the conclusion holds by Observation 2.1. This completes the proof. ◻
Next, we focus on connected coalition partitions of graphs with cut vertices.
Lemma 2.2. Let \(G\) be a graph and \(\Phi\) be a \(CC(G)\)-partition of \(G\). If \(A\in \Phi\) and \(B\in \Phi\) form a connected coalition of \(G\), then \(v\in A\) or \(v\in B\) for every cut vertex \(v\) of \(G\).
Proof. Suppose to the contrary that \(v\notin A\) and \(v\notin B\) for some cut vertex \(v\) of \(G\). Let \(G_{1},G_{2},\ldots,G_{k}\) (\(k\geq 2\)) be the connected components of \(G-v\). If there is a connected component \(G_{i}\) with \(1\leq i\leq k\) such that \(A\cup B\subseteq V(G_{i})\), then the vertices in \(\cup _{j\neq i}V(G_{j})\) are not dominated by \(A\cup B\). This contradicts that \(A\) and \(B\) form a connected coalition of \(G\). Otherwise, \(G[A\cup B]\) is not connected, which again contradicts that \(A\) and \(B\) form a connected coalition of \(G\). Therefore, \(v\in A\) or \(v\in B\). This completes the proof. ◻
Lemma 2.3. Let \(G\) be a connected graph of \(CC(G)\geq 3\) with no full vertex and let \(\Phi\) be a \(CC(G)\)-partition of \(G\). Then \(v\) and \(w\) belong to the same set in \(\Phi\) for any two distinct cut vertices \(v\) and \(w\) of \(G\).
Proof. Since \(G\) is a connected graph with no full vertex and \(CC(G)\geq 3\), there is a set \(A\in \Phi\) such that \(v\notin A\) and \(w\notin A\). Further, there is a set \(B\in \Phi\) such that \(A\) and \(B\) form a connected coalition of \(G\). Therefore, by Lemma 2.2, \(v\in B\) and \(w\in B\). This completes the proof. ◻
Finally, we give an observation that will be useful later.
Observation 2.4. Let \(G\) be a connected graph with no full vertex, and let \(A\subseteq V(G)\) with \(|A|\geq 2\) be a connected dominating set of \(G\). Then there is a partition \(\Phi=\{A_{1},A_{2},\ldots,A_{k}\}\) of \(A\) such that for any \(A_{i}\in \Phi\), \(A_{i}\) and \(A_{j}\) form a connected coalition of \(G\) for some \(A_{j}\in \Phi\).
Proof. Let \(X\subseteq A\) be a minimal connected dominating set of \(G\), that is, \(X'\) is not a connected dominating set of \(G\) for any proper subset \(X'\subseteq X\). Note that \(\mid X\mid \geq 2\) due to no full vertex of \(G\). Then \(X_{1}\) and \(X_{2}\) form a connected coalition of \(G\) for any partition \(\{X_{1},X_{2}\}\) of \(X\), in which \(\mid X_{1}\mid\geq1\) and \(\mid X_{2}\mid\geq1\). If \(X=A\), then we are done. Thus, we consider that \(A\backslash X\neq \emptyset\).
Let \(A\backslash X=\{x_{1},x_{2},\ldots ,x_{s}\}\) and \(Y_{r}=X\cup \{x_{1},x_{2},\ldots ,x_{r}\}\) for any \(r\leq s\). Clearly, if \(r=0\), then \(Y_{r}=X\). Assume that there is a partition \(\Phi_{r}=\{A_{1},A_{2},\ldots,A_{t}\}\) of \(Y_{r}\) such that for any \(A_{i}\in \Phi_{r}\), \(A_{i}\) and \(A_{j}\) form a connected coalition of \(G\) for some \(A_{j}\in \Phi_{r}\). If \(\{x_{r+1}\}\cup A_{i}\) is a connected dominating set of \(G\) for some \(i\in \{1,2,\ldots,t\}\), then let \(\Phi_{r+1}=\{A_{1},A_{2},\ldots,A_{t},\{x_{r+1}\}\}\), otherwise let \(\Phi_{r+1}=\{A_{1}\cup\{x_{r+1}\},A_{2},\ldots,A_{t}\}\). It is easy to see that \(\Phi_{r+1}\) is a partition of \(Y_{r+1}\) such that for any \(A_{i}'\in \Phi_{r+1}\), \(A_{i}'\) and \(A_{j}'\) form a connected coalition of \(G\) for some \(A_{j}'\in \Phi_{r+1}\). Following this step for all vertices in \(\{x_{1},x_{2},\ldots ,x_{s}\}\) until \(r=s\), we can obtain a partition \(\Phi=\{A_{1},A_{2},\ldots,A_{k}\}\) of \(A\) such that for any \(A_{i}\in \Phi\), \(A_{i}\) and \(A_{j}\) form a connected coalition of \(G\) for some \(A_{j}\in \Phi\). This completes the proof. ◻
Proof of Theorem 1.5. We first prove the sufficiency. It is clear that \(CC(G)\geq2\) by Theorem 1.3. Assume that \(CC(G)\geq3\). Let \(\Phi\) be a \(CC(G)\)-partition of \(G\). By Lemma 2.3, there is a set \(A\in \Phi\) such that \(X\subseteq A\). Then \(A\) is a connected dominating set of \(G\) since \(X\) is a connected dominating set of \(G\). This contradicts that \(\Phi\) is a connected coalition partition of \(G\). Hence, \(CC(G)=2\).
Next, we prove the necessity. Suppose to the contrary that \(X\) is not a connected dominating set of \(G\). Let \(Y\) be a minimal connected dominating set of \(G\) with \(X\subseteq Y\). Then \(Y\backslash X\neq \emptyset\). If \(V(G)\backslash Y\) is not a connected dominating set of \(G\), then let \(\Phi=\{Y\backslash \{v\}, \{v\}, V(G)\backslash Y\}\) for some \(v\in Y\backslash X\). Since \(v\notin X\), \((Y\backslash \{v\})\cup(V(G)\backslash Y)=V(G)\backslash\{v\}\) is a connected dominating set of \(G\). This implies that \(\Phi\) is a connected coalition partition of \(G\). Therefore, \(CC(G)\geq 3\), a contradiction. Assume that \(V(G)\backslash Y\) is a connected dominating set of \(G\). Since \(G\) has no full vertex, \(\mid V(G)\backslash Y\mid\geq 2\). By Observation 2.4, we know that there is a partition \(\{Y_{1},Y_{2},\ldots,Y_{k}\}\) of \(V(G)\backslash Y\) such that for any \(Y_{i}\), \(Y_{i}\) and \(Y_{j}\) form a connected coalition of \(G\) for some \(Y_{j}\in \{Y_{1},Y_{2},\ldots,Y_{k}\}\). This implies that \(\Phi=\{Y\backslash \{v\}, \{v\}, Y_{1},\ldots,Y_{k}\}\) is a connected coalition partition of \(G\) for some \(v\in Y\). Therefore, \(CC(G)\geq 4\), again a contradiction. This proves Theorem 1.5. ◻
We close this section with a brief proof of Theorem 1.4 and Corollary 1.8 by using Theorem 1.5.
Proof of Theorem 1.4. Let \(X=\{v\in V(T)\mid T-v \ \text{is not connected}\}\), that is, \(X\) contains all of vertices other than pendant vertices of \(T\). Clearly, \(X\) is a connected dominating set of \(T\). Therefore, by Theorem 1.5, we have \(CC(T)=2\). This completes the proof. ◻
Proof of Corollary 1.8. Assume that \(V(G)=\{v\}\). Then \(v\) is a full vertex of \(G\circ H\). By Observation 2.1, \(CC(G\circ H)=0\) if \(CC(H)=0\) and \(CC(G\circ H)=1+CC(H)\) if \(CC(H)\neq0\).
We now need only to consider that \(\mid V(G)\mid\geq 2\). It is easy to see that \(G\circ H\) has no full vertex. Let \(X=\{v\in V(G\circ H)\mid G\circ H-v \ \text{is not connected}\}\). Obviously, \(X=V(G)\) and \(X\) is a connected dominating set of \(G\circ H\). Thus, \(CC(G\circ H)=2\) by Theorem 1.5. This completes the proof. ◻
In this section, we study the connected coalition number of unicycle graphs by proving Theorem 1.10. We start with the connected coalition number of cycles.
Lemma 3.1. For any cycle \(C_{n}\) with order \(n\), we have \[CC(C_{n})=\left\{\begin{array}{ll} 4, &\text{if $n=4$},\\ 3,&\text{otherwise}. \end{array}\right.\]
Proof. Let \(C_{n}=v_{1}v_{2}\cdots v_{n}v_{1}\). It is easy to check that \(CC(C_{3})=3\) and \(CC(C_{4})=4\). Thus, we assume that \(n\geq 5\). It is not hard to see that \(\{\{v_{2}\},\{v_{n}\},V(C_{n})\backslash \{v_{2},v_{n}\}\}\) is a connected coalition partition of \(G\). Hence, \(CC(C_{n})\geq 3\). We now need only to prove that \(CC(C_{n})\leq3\). Suppose to the contrary that \(CC(C_{n})\geq 4\). Let \(\Phi\) be a \(CC(C_{n})\)-partition of \(C_{n}\).
Note that the subgraph induced by a connected dominating set of \(C_{n}\) is either the cycle \(C_{n}\) or a path \(P_{n-1}\) or a path \(P_{n-2}\). Since \(CC(C_{n})\geq 4\), for any two sets in \(\Phi\), say \(A\) and \(B\), we have \(C_{n}[A\cup B]=P_{n-2}\). Without loss of generality, we assume that \(P_{n-2}=v_{1}v_{2}\cdots v_{n-2}\). In this way, \(\{v_{n-1}\}\in \Phi\) and \(\{v_{n}\}\in \Phi\) since \(CC(C_{n})\geq 4\). Note that \(\{v_{n-1},v_{n}\}\) is not a dominating set of \(C_{n}\). Then either \(\{v_{n-1}\}\cup A\) or \(\{v_{n-1}\}\cup B\) is a connected dominating set of \(C_{n}\). This implies that \(\Phi=\{\{v_{1}\},\{v_{2},v_{3},\ldots,v_{n-2}\},\{v_{n-1}\},\{v_{n}\}\}\). However, none of \(\{v_{1},v_{n}\}\), \(\{v_{2},v_{3},\ldots,v_{n-2},v_{n}\}\) and \(\{v_{n-1},v_{n}\}\) is a connected dominating set of \(C_{n}\), which contradicts that \(\Phi\) is a connected coalition partition of \(C_{n}\). Therefore, \(CC(C_{n})\leq3\) and so \(CC(C_{n})=3\). This completes the proof. ◻
We now discuss about the relation of the connected coalition number between graphs \(G\) with pendant vertices \(X\) and graphs \(G-X\).
Lemma 3.2. Let \(H\) be a connected graph of order \(n\geq 3\) with no full vertex. If \(G\) is a graph obtained by identifying a vertex of \(H\) and a vertex of \(K_{2}\), then \(CC(G)\leq CC(H)\).
Proof. By Theorem 1.3, we know that \(CC(G)\geq 2\). Let \(v\) be the pendant vertex of \(G\) that comes from \(K_{2}\), and \(w\) be the neighborhood of \(v\) in \(G\). Let \(\Phi=\{A_{1},A_{2},\ldots,A_{CC(G)}\}\) be a \(CC(G)\)-partition of \(G\) that satisfies \(w\in A_{1}\) and \(\mid A_{1}\mid\) is maximum, that is, for every \(CC(G)\)-partition \(\{B_{1},B_{2},\ldots,B_{CC(G)}\}\) of \(G\), if \(w\in B_{1}\), then \(\mid A_{1}\mid \geq\mid B_{1}\mid\). We say that \(\{v\}\notin \Phi\). If not, then \(\{v\}\) and \(A_{1}\) form a connected coalition of \(G\) by Lemma 2.2. This implies that \(A_{1}\) is a connected dominating of \(G\), which contradicts that \(\Phi\) is a connected coalition partition of \(G\).
Let \(\Phi'=\{A'_{1},A'_{2},\ldots,A'_{CC(G)}\}\), where \(A'_{i}=A_{i}\backslash\{v\}\) for all \(i=\{1,2,\ldots,\) \(CC(G)\}\). Since \(A_{1}\) is not a connected dominating set of \(G\), \(A'_{1}\) is not a connected dominating set of \(H\). Define \[I=\{i\in\{2,3,\ldots,CC(G)\}\mid A'_{i} \ \text{is not a connected dominating set of} \ H\}.\]
We separate the proof into two cases.
Case 1. \(I\neq \emptyset\).
Let \(\{A'_{j_{1}},A'_{j_{2}},\ldots,A'_{j_{k}}\}\) be a partition of \(A'_{j}\) that satisfies the condition in Observation 2.4 for all \(j\in \{2,3,\ldots,CC(G)\} \backslash I\). A partition \(\Psi\) of \(V(H)\) is constructed as follows:
(i) \(A'_{1}\in \Psi\);
(ii) \(A'_{i}\in \Psi\) for all \(i\in I\);
(iii) \(\{A'_{j_{1}},A'_{j_{2}},\ldots,A'_{j_{k}}\} \subseteq \Psi\) for all \(j\in \{2,3,\ldots,CC(G)\} \backslash I\).
Recall that \(w\in A_{1}\) and \(w\) is a cut vertex of \(G\). By Lemma 2.2, \(A_{1}\) and \(A_{i}\) form a connected coalition of \(G\) for all \(i\in \{2,3,\ldots,CC(G)\}\). Then \(A'_{1}\) and \(A'_{j}\) form a connected coalition of \(H\) for all \(j\in I\). Therefore, \(\Psi\) is a connected coalition partition of \(H\), and so \(CC(G)\leq \mid\Psi\mid\leq CC(H)\).
Case 2. \(I=\emptyset\).
Recall that \(A'_{1}\) is not a connected dominating set of \(H\). We now divided the proof into two subcases.
Subcase 2.1. \(A'_{1}\cup \{u\}\) is a connected dominating set of \(H\) for some \(u\in V(H)\backslash A'_{1}\).
In this case, without loss of generality, we assume that \(u\in A'_{2}\). Let \(\{A'_{j_{1}},A'_{j_{2}},\ldots,A'_{j_{k}}\}\) is a partition of \(A'_{j}\) that satisfies the condition in Observation 2.4 for all \(j\in \{3,\ldots,CC(G)\}\). A partition \(\Psi\) of \(V(H)\) is constructed as follows:
(i) \(A'_{1}\in \Psi\) and \(\{u\}\in \Psi\);
(ii) \(\{A'_{j_{1}},A'_{j_{2}},\ldots,A'_{j_{k}}\}\subseteq \Psi\) for all \(j\in \{3,\ldots,CC(G)\}\);
(iii) If \(A'_{2}\backslash \{u\}\) is not a connected dominating set of \(H\), then we take \(A'_{2}\backslash \{u\}\in \Psi\). If \(A'_{2}\backslash \{u\}\) is a connected dominating set of \(H\), then we take \(\{A'_{2_{1}},A'_{2_{2}},\ldots,A'_{2_{k}}\}\subseteq \Psi\), where \(\{A'_{2_{1}},A'_{2_{1}},\ldots,A'_{2_{k_{2}}}\}\) is a partition of \(A'_{2}\backslash \{u\}\) that satisfies the condition in Observation 2.4.
It is obvious that \(\Psi\) is a connected coalition partition of \(H\). Therefore, \(CC(G)\leq \mid\Psi\mid\leq CC(H)\).
Subcase 2.2. \(A'_{1}\cup \{u\}\) is not a connected dominating set of \(H\) for all vertex \(u\in V(H)\backslash A'_{1}\).
Since \(H\) has no full vertex and \(I=\emptyset\), \(\mid A'_{2}\mid\geq 2\). For a vertex \(u\in A'_{2}\), a partition \(\Theta\) of \(V(G)\) is constructed as follows:
(i) \(A_{1}\cup \{u\}\in \Theta\);
(ii) \(A_{2}\backslash \{u\}\in \Theta\);
(iii) \(A_{i}\in \Theta\) for all \(i\in \{3,\ldots,CC(G)\}\).
Since \(A'_{1}\cup \{u\}\) is not a connected dominating set of \(H\), \(A_{1}\cup \{u\}\) is not a connected dominating set of \(G\). By Lemma 2.2, \(A_{1}\) and \(A_{i}\) form a connected coalition of \(G\) for all \(i\in \{2,3,\ldots,CC(G)\}\). Therefore, \(\Theta\) is a \(CC(G)\)-partition of \(G\). However, \(\mid A_{1}\cup \{u\}\mid\geq \mid A_{1}\mid\), which contradicts the choice of the set \(A_{1}\). This proves Lemma 3.2. ◻
Proof of Theorem 1.10. By Lemma 3.1 and Observation 2.1, the conclusion holds for \(G=C_{3}\), \(G=C_{4}\) and \(G\in \mathcal{G}\). Thus, we assume that \(G\) has no full vertex and \(n\geq 5\).
Let \(X=\{v\in V(G)\mid G-v\ \text{is not connected}\}\) and \(Z=\{v\in V(G)\mid deg(v)=1\}\). Then \(V(G)=X\cup Y\cup Z\). It is easy to see that if \(\mid Y \mid\leq 1\) or \(G[Y]=K_{2}\), then \(X\) is a connected dominating set of \(G\). Therefore, \(CC(G)=2\) by Theorem 1.5.
We now need only to consider that \(\mid Y\mid \geq 3\) and \(Y\) consists of two non-adjacent vertices of \(C_{m}\). Let \(C_{m}=v_{1}v_{2}\cdots v_{m}v_{1}\). It is obvious that \(m\geq 4\) and if \(\mid Y\mid\geq 3\), then \(Y\) contains two non-adjacent vertices of \(C_{m}\). Without loss of generality, we assume that \(v_{i},v_{j}\in Y\) and \(v_{i}v_{j}\notin E(G)\) for some \(i,j\in \{1,2,\ldots,m\}\). Let \(C_{4}+e\) be the graph obtained by identifying a vertex of \(C_{4}\) and a vertex of \(K_{2}\), see Fig. 1 (b). It is not hard to check that \(CC(C_{4}+e)=3\). By Lemmas 3.1 and 3.2, \(CC(G)\leq CC(C_{m})=3\) if \(m\geq 5\) and \(CC(G)\leq CC(C_{4}+e)=3\) if \(m=4\). On the other hand, note that \(G-\{v_{i},v_{j}\}\) is not connected. Therefore, \(\{\{v_{1}\},\{v_{k}\},V(G)\backslash\{v_{1},v_{k}\}\}\) is a connected coalition partition of \(G\) and so \(CC(G)=3\). This completes the proof. ◻
The Cartesian product of two graphs \(G\) and \(H\), denoted by \(G\Box H\), is defined as the vertex set \(V(G)\times V(H)=\{(u,v)\mid u\in V(G),v\in V(H)\}\) with an edge between vertices \((u_{1},v_{1})\) and \((u_{2},v_{2})\) if either \(v_{1}\) is adjacent to \(v_{2}\) in \(H\) and \(u_{1}=u_{2}\), or \(u_{1}\) is adjacent to \(u_{2}\) in \(G\) and \(v_{1}=v_{2}\).
Theorem 4.1. Let \(G\) and \(H\) be two connected graphs with at least two vertices. Then \(CC(G\Box H)\geq \max\{CC(G)+k_{G},CC(H)+k_{H}\}\), where \(k_{G}\) and \(k_{H}\) denote the number of full vertices in \(G\) and \(H\), respectively.
Proof. Without loss of generality, we assume that \(CC(G)+k_{G}\geq CC(H)+k_{H}\). Since \(G\) has at least two vertices, \(G\Box H\) has no full vertex. Moreover, since \(G\) and \(H\) are two connected graphs, \(G\Box H\) is also connected. Let \(u_{1},u_{2},\ldots,u_{k_{G}}\) be all of the full vertices of \(G\).
We first consider that \(CC(G)=0\). Since \(G\) is a connected graph, \(k_{G}\geq 1\). Let \(P_{i}=\{(u,v)\in V(G)\times V(H)\mid u=u_{i}, v\in V(H)\}\) for \(i\in \{1,2,\ldots,k_{G}-1\}\) and \(P_{k_{G}}=V(G\Box H)\setminus(\cup_{i=1}^{k_{G}-1}V(P_{i}))\). Then \(P_{i}\) is a connected dominating set of \(G\Box H\) for every \(i\in \{1,2,\ldots,k_{G}\}\). Further, since \(H\) has at least two vertices, \(\mid P_{i}\mid\geq 2\). Therefore, we can obtain a connected coalition partition of \(G\Box H\) with the cardinality at least \(2k_{G}\) by Observation 2.4. Hence, \(CC(G\Box H)\geq2k_{G}\geq CC(G)+k_{G}\).
Recall that \(CC(G)=1\) if and only if \(G=K_{1}\) for any graph \(G\). Thus, we now need only to consider that \(CC(G)\geq 2\). Let \(\Phi=\{A_{1},A_{2},\ldots,A_{CC(G)}\}\) be a \(CC(G)\)-partition of \(G\) and \(Q_{i}=\{(u,v)\in V(G)\times V(H)\mid u\in A_{i},v\in V(H)\}\) for all \(i\in \{1,2,\ldots,CC(G)\}\). Without loss of generality, we assume that \(A_{i}=\{u_{i}\}\) for all \(i\in \{1,2,\ldots,k_{G}\}\). Note that \(Q_{i}\) is a connected dominating set of \(G\Box H\) for all \(i\in \{1,\ldots,k_{G}\}\). Moreover, \(\mid B_{i}\mid \geq 2\) due to \(\mid V(G)\mid\geq 2\). This implies that there exists a partition \(\{Q_{i_{1}},Q_{i_{2}},\ldots,Q_{i_{k_{i}}}\}\) of \(Q_{i}\) satisfying the condition in Observation 2.4. A partition \(\Psi\) of \(V(G\Box H)\) is constructed as follows:
(i) \(Q_{i}\in \Psi\) for all \(i\in \{k_{G}+1,k_{G}+2,\ldots,CC(G)\}\);
(ii) \(\{Q_{i_{1}},Q_{i_{2}},\ldots,Q_{i_{k}}\} \subseteq \Psi\) for all \(i\in \{1,2,\ldots,k_{G}\}\).
Note that for any \(A_{i}\in \Phi\), there exists an \(A_{j}\in \Phi\) such that \(A_{i}\) and \(A_{j}\) form a connected coalition of \(G\), where \(i,j\in \{k_{G}+1,k_{G}+2,\ldots,CC(G)\}\) and \(i\neq j\). Therefore, \(Q_{i}\) and \(Q_{j}\) also form a connected coalition of \(G\Box H\). This implies that \(\Psi\) is a connected coalition partition of \(G\Box H\). Hence, \(CC(G\Box H)\geq\mid\Phi\mid\geq (CC(G)-k_{G})+2k_{G} \geq CC(G)+k_{G}\). This completes the proof. ◻
We next improve the lower bound in Theorem 4.1 for the connected coalition number of the Cartesian product of two special graphs.
Theorem 4.2. Let \(G\) and \(H\) be two graphs with order \(n\geq 2\) and \(m\geq 2\), respectively. If there is a full vertex \(u\) in \(G\) such that \(G-u\) is connected, and there is a full vertex \(v\) in \(H\) such that \(H-v\) is also connected, then \(CC(G\Box H)\geq m+n-1\).
Proof. Let \(V(G)=\{u_{1},u_{2},\ldots,u_{n}\}\) and \(V(H)=\{v_{1},v_{2},\ldots,v_{m}\}\). Without loss of generality, we assume \(u=u_{1}\) and \(v=v_{1}\). Let \(A_{1}=\{(x,y)\in V(G)\times V(H)\mid x=u_{1} \ \text{and} \ y=v_{1}, \ \text{or}\ x\neq u_{1} \ \text{and} \ y\neq v_{1}\}\), \(A_{i}=\{(u_{i},v_{1})\}\) for all \(i=2,3,\ldots,n\), and \(A_{i}=\{(u_{1},v_{i-n+1})\}\) for all \(i=n+1,n+2,\ldots,m+n-1\). Then \(A_{1}\) and \(A_{i}\) form a connected coalition of \(G\Box H\) for all \(i=2,3,\ldots,m+n-1\). This implies that \(\{A_{1},A_{2},\ldots,A_{m+n-1}\}\) is a connected coalition partition of \(G\Box H\). Hence, \(CC(G\Box H)\geq m+n-1\). ◻
The lexicographic product of two graphs \(G\) and \(H\), denoted by \(G\circ H\), is defined as the vertex set \(V(G)\times V(H)\) with an edge between vertices \((u_{1},v_{1})\) and \((u_{2},v_{2})\) if either \(v_{1}\) is adjacent to \(v_{2}\) in \(H\) and \(u_{1}=u_{2}\), or \(u_{1}\) is adjacent to \(u_{2}\) in \(G\).
Theorem 4.3. Let \(G\) and \(H\) be two graphs with at least two vertices. Then \(CC(G\circ H)\geq CC(G)+k_{G}\), where \(k_{G}\) is the number of full vertices in \(G\).
Proof. Clearly, \(CC(G)\neq 1\). Similar to the proof in Theorem 4.1, we can obtained a connected coalition partition of the cardinality at least \(2k_{G}\) for \(CC(G)=0\) and the cardinality at least \(CC(G)+k_{G}\) for \(CC(G)\geq 2\), respectively. ◻
We thank the anonymous referees for their support and valuable feedback. Xiaxia Guan was supported by the Natural Science Foundation of Shanxi Province [No. 202403021222034]. Maoqun Wang was supported by the National Natural Science Foundation of China [No. 12301455] and Natural Science Foundation of Shandong Province [No. ZR2023QA080].