(PDF) Connected coalitions in graphs

Connected coalitions in graphs arXiv:2302.05754v1 [math.CO] 11 Feb 2023 Saeid Alikhani1 , Davood Bakhshesh2 , Hamidreza Golmohammadi3 , Elena V. Konstantinova3,4 February 14, 2023 1 Department of Mathematical Sciences, Yazd University, 89195-741, Yazd, Iran of Computer Science, University of Bojnord, Bojnord, Iran 3 Novosibirsk State University, Pirogova str. 2, Novosibirsk, 630090, Russia 4 Sobolev Institute of Mathematics, Ak. Koptyug av. 4, Novosibirsk, 630090, Russia 2 Department

e

Abstract The connected coalition in a graph G = (V, E) consists of two disjoint sets of vertices V1 and V2 , neither of which is a connected dominating set but whose union V1 ∪V2 , is a connected dominating set. A connected coalition partition in a graph G of order n = |V | is a vertex partition ψ = {V1 , V2 , ..., Vk } such that every set Vi ∈ ψ either is a connected dominating set consisting of a single vertex of degree n − 1, or is not a connected dominating set but forms a connected coalition with another set Vj ∈ ψ which is not a connected dominating set. The connected coalition number, denoted by CC(G), is the maximum cardinality of a connected coalition partition of G. In this paper, we initiate the study of connected coalition in graphs, and present some basic results. Precisely, we characterize all graphs that have a connected coalition partition. Moreover, we show that for any graph G of order n with δ(G) = 1 and with no full vertex, it holds that CC(G) < n. Furthermore, we show that for any tree T , CC(T ) = 2. Finally, we present two polynomialtime algorithms that for a given connected graph G of order n determine whether CC(G) = n or CC(G) = n − 1. Keywords: Coalition; coalition partition coalition; Tree; Corona product. AMS Subj. Class.: 05C60. 1 Introduction Let G = (V, E) be a simple graph with the vertex set V and the edge set E. The open neighborhood of a vertex v ∈ V is defined as N (v) = u | uv ∈ E, and its closed neighborhood as N [v] = N (v) ∪ v. Each vertex u ∈ N (v) is referred to as a neighbor of v, and |N (v)| is referred to as the degree of v, denoted by deg(v). A vertex v in G is considered pendant if its open neighborhood N (v) has only one vertex. This vertex is 1 referred to as the support vertex of v, denoted by support(v). An edge is considered pendant if one of its vertices is pendant. In a tree T , a vertex of degree one is referred to as a leaf, and the vertex adjacent to it is referred to as a support vertex. The set of leaves in a tree T is denoted by L(T ), and its cardinality by l(T ). In a graph G with n = |V | vertices, a vertex of degree n − 1 is referred to as a full or universal vertex, and a vertex of degree 0 is referred to as an isolate. The minimum degree of a graph G is denoted by δ(G), and the maximum degree by ∆(G). A subset Vi ⊆ V is referred to as a singleton set if |Vi | = 1, or a non-singleton set if |Vi | ≥ 2. A graph without any isolated vertices is referred to as a non-isolated graph. A set S ⊆ V in a graph G is considered to be a dominating set if every vertex in V \ S has at least one neighbor in the set S. A connected dominating set D is defined as a dominating set such that the subgraph induced by the vertices in D is connected. The connected domination number, denoted by γc (G), is the minimum size of a connected dominating set in the graph G. Connected domination was first introduced in 1979 by Sampathkumar and Walikar, based on a suggestion by S.T. Hedetniemi [14]. Over the past two decades, it has garnered significant interest due to its important applications in Wireless Sensor Networks. For more information, readers are referred to the literature including [11, 12, 13]. A domatic partition is a partition of the vertex set into dominating sets. The connected domatic partition is a similar partition into connected dominating sets. The maximum size of a domatic partition is called the domatic number, denoted by d(G). The maximum size of a connected domatic partition is called the connected domatic number, denoted by dc (G). The domatic number was first introduced by Cockayne and Hedetniemi [5], and the connected domatic number was introduced by Zelinka in [17]. Further information on these concepts can be found in sources such as [7, 15, 16, 17]. The idea of coalitions and coalition partitions was first introduced in [8] and has since then been studied in the field of graph theory, as seen in works such as [2, 4, 9, 10]. The definition of coalitions and coalition partitions were based on general graph properties, but the main focus was on their relation to the concept of dominating sets. A coalition π in a graph G is defined as two disjoint sets of vertices, V1 and V2 , that individually cannot dominate the graph, but their union V1 ∪ V2 is able to dominate the graph. The sets V1 and V2 are referred to as coalition partners in π. A coalition partition, also known as c-partition, in a graph G is a partition of the vertices of G into sets π = {V1 , V2 , . . . , Vk } such that each Vi in π is either a singleton dominating set of G or a non-dominating set that forms a coalition with another non-dominating set Vj ∈ π. The coalition number C(G) of a graph is the maximum number of sets that can be present in a c-partition of G. A c-partition of G with C(G) sets is referred to as a C(G)-partition. For every c-partition π of a graph G, there is a corresponding graph called the coalition graph of G with respect to π, denoted as CG(G, π). The vertices of this graph correspond one-to-one with the sets of π, and two vertices are adjacent in CG(G, π) if and only if their corresponding sets form a coalition. The study of coalition graphs, particularly for paths, cycles, and trees, was conducted in [9]. The concept of total coalition was introduced and explored in [1], while the coalition parameter for cubic 2 graphs of order at most 10 was investigated in [2]. According to Section 4 of reference [8], there are open problems and areas for future research which suggest exploring connected dominating c-partition. Inspired by this, our focus is on the examination of connected coalitions and their partitions. In Section 2, we define and discuss some properties of connected coalitions. In Section 3, we determine the connected coalition number of graphs with pendant edge. Furthermore, we consider the connected coalition of trees in Section 4. In Section 5, we present two polynomial-time algorithms that for a given connected graph G of order n determine whether CC(G) = n or CC(G) = n − 1. Finally, we present some open problems for future works in Section 6. 2 Introduction to connected coalition In this section, we first state the definition of the connected coalition and connected coalition partition. Definition 2.1 (Connected coalition) For a graph G with vertex set V , two sets V1 , V2 ⊆ V form a connected coalition, if neither V1 nor V2 is a connected dominating set but V1 ∪ V2 is a connected dominating set in G. Definition 2.2 (Connected coalition partition) A connected coalition partition in a graph G is a vertex partition ψ = {V1 , V2 , . . . , Vk } such that every set Vi of ψ either is a connected dominating set consisting of a single vertex of degree n − 1, or is not a connected dominating set but forms a connected coalition with another set Vj ∈ ψ which is not a connected dominating set. The maximum cardinality of a connected coalition partition of G is called the connected coalition number of G, denoted by CC(G). A connected c-partition of a graph G with the cardinality CC(G) is denoted by CC(G)partition. Considering the graph G should be connected, we have the following trivial observation. Observation 2.3 For any disconnected graph G of order n ≥ 2, we have CC(G) = 0. Now, by the following Theorem we characterize the graphs G having C(G) = 1. Lemma 2.4 For any graph G, CC(G) = 1 if and only if G = K1 . Proof. If CC(G) = 1, then {V } is a CC(G)-partition. By Definition 2.2, we must have |V | = 1. So, it is clear that G = K1 . Conversely, if G = K1 , clearly we have CC(G) = 1. Now, we prove the following lemma. Lemma 2.5 If G is a connected graph of order n > 1 with no full vertex, then CC(G) ≥ 2dc (G). 3 Proof. Let D = {D1 , D2 , . . . , Dk } be a connected domatic partition of a graph G, where k = dc (G). Since G has no full vertex, all sets Di are not singletons. Now, we can suppose that D1 , D2 , . . . , Dk−1 are minimal connected dominating sets of G; if any set Di , for 1 ≤ i ≤ k − 1, is not a minimal connected dominating set, let Di0 ⊆ Di be a minimal connected dominating set contained in Di and add the vertices in Di \ Di0 to Dk . Note that any partition of a non-singleton, minimal connected dominating set into two nonempty sets creates two non-connected dominating sets whose union forms a connected coalition. Therefore, for every 1 ≤ i ≤ k − 1, we can partition every non-singleton set Di into two sets Di,1 , and Di,2 , which form a connected coalition. Doing this for each Di , for 1 ≤ i ≤ k − 1, we obtain a collection D0 of sets, each of which is either a connected dominating set consisting of a single vertex of degree n − 1 or is a non-connected dominating set that forms a coalition with another nonconnected dominating set in D0 . Now we can consider the connected dominating set Dk . If Dk is a minimal connected dominating set, then we can partition it into two non-connected dominating sets, add these two sets to D0 and create a connected cpartition of G of order at least k + 1 > dc (G). If Dk is not a minimal connected dominating set, let Dk0 ⊆ Dk be a minimal connected dominating set contained in Dk , 0 ∪ D0 partition Dk0 = Dk,1 k,2 into two non-empty, non-connected dominating sets, which 0 0 to and Dk,2 together form a connected coalition, and let Dk00 = Dk \ Dk0 and add Dk,1 0 00 D . It follows that Dk is not a connected dominating set, else there are at least k + 1 disjoint connected dominating sets in G, a contradiction, since k = dc (G). If Dk00 forms a connected coalition with any non-connected dominating set, then adding Dk00 to D0 , we have a connected c-partition of G of order at least k + 2 > dc (G). However, if Dk00 0 from D0 and does not form a connected coalition with any set in D0 , then remove Dk,2 0 00 0 add the set Dk,2 ∪Dk , to D , therefore we create a connected c-partition of G of order at least k + 1 > dc (G). Now, based on above construction of a connected c-partition of G, the number of the elements of this partition is minimized when each set Di (1 ≤ i ≤ k) is partitioned into two sets. Hence, it holds that CC(G) ≥ 2dc (G). It is remarkable that for any graph G, dc (G) ≥ 1. Based on Lemma 2.5, we have the following result. Theorem 2.6 If G is a connected graph of order n > 1 with no full vertex, then CC(G) ≥ 2. By Theorem 2.6, we immediately conclude the following result. Corollary 2.7 If G is a connected graph with CC(G) < 2, then G has at least one full vertex. Our immediate aim in this paper is to investigate the possibility of the existence of a connected c-partition of a graph G. For this purpose, we define a family of a graphs, denoted by F, in the following. For any two graphs G and H, let G + H be the join of two graphs G and H which is a graph constructed from disjoint copies of G and H by connecting each vertex of G to each vertex of H. Now, we state the following definition. 4 Definition 2.8 A family F of graphs is constructed as follows: • Step 1. We add all disconnected graphs G of order n ≥ 2 into F. • Step 2. For any graph G ∈ F, we add G + K1 into F. It is remarkable that the family F contains both many disconnected graphs and many connected graphs. For instance, Figure 1 shows a connected graph in F. As another example, consider the the friendship graphs Fn which is a graph with 2n + 1 vertices and 3n edges, formed by the join of K1 + nK2 . Based on Definition 2.8, we have Fn ∈ F. Figure 1: A connected graph in F. Now, we prove the following Lemma. Lemma 2.9 For any graph G, if G ∈ F, then CC(G) = 0. Proof. Using induction on the number of full vertices of G, we prove that CC(G) = 0. For the base step, if G has no full vertex, then since G ∈ F, G is a disconnected graph of order n ≥ 2. By Observation 2.3, we have CC(G) = 0. For the induction hypothesis step, suppose that for any graph H ∈ F such that the number of its full vertices is less than the number of full vertices of G, it holds that CC(H) = 0. For induction step, suppose that G = H + K1 , where H ∈ F. Let u be the vertex of K1 . By induction hypothesis, we have CC(H) = 0. Now, if CC(G) 6= 0, since G 6= K1 , by Lemma 2.4, we must have CC(G) ≥ 2. Since u is the full vertex of G, the set {u} belongs to any CC(G)-partition ψ. Now, by removing {u} of ψ, we obtain a c-partition for H with CC(H) ≥ 1, which is a contradiction. Thus, CC(G) = 0. The next theorem shows a necessary and sufficient condition for the existence of a connected c-partition of a graph G. Theorem 2.10 For any graph G, CC(G) = 0 if and only if G ∈ F. Proof. By Corollary 2.7, since we assume that C(G) < 2, G has at least one full vertex. Now, if G ∈ F, by Lemma 2.9, we have CC(G) = 0, Conversely, suppose that CC(G) = 0. To prove G ∈ F, we use the induction on the number of full vertices of G. For the base step, we assume that G contains exactly one full vertex u. Now, consider the graph G0 = G[V \{u}]. If G0 is a connected graph, since G0 has no full vertex, by 5 Theorem 2.6, CC(G0 ) ≥ 2. Hence, using a CC(G0 )-partition and the singleton set {u}, we can construct a CC(G)-partition with CC(G) ≥ 3, which is a contradiction. Hence, G0 must be disconnected. Hence, by the definition of F, we have G ∈ F. For induction hypothesis, we assume that if G0 is a connected graph with CC(G0 ) = 0 such that the number of its full vertices is less than G, then G0 ∈ F. Now, we prove the induction step. Let u be the full vertex of G. Consider the graph G0 = G[V \{u}]. Now, we have two cases. • Case 1. G0 is disconnected. Then, by the definition of F, G ∈ F. • Case 2. G0 is connected. Since CC(G) = 0, we must have CC(G0 ) = 0, because otherwise, similar to the above arguments, using a CC(G0 ) -partition and the singleton set {u}, we can construct a CC(G)-partition with CC(G) ≥ 3, which is a contradiction. Now, since G0 is connected and CC(G0 ) = 0, by Corollary 2.7, G0 has at least one full vertex. It is clear that the number of full vertices of G0 is less than the number of full vertices of G. Then, by induction hypothesis, G0 ∈ F. Hence, by the definition of F, we can see G ∈ F. This completes the proof. By Theorem 2.10 and Lemma 2.4, we have the following corollaries. Corollary 2.11 If G 6∈ F is a connected graph, then 1 ≤ CC(G) ≤ n. As before, we know that K1 attains the lower bound of Corollary 2.11, while the complete graphs Kn and the complete bipartite graphs Kr,s for 2 ≤ r ≤ s such that r + s = n, attain the upper bound. Corollary 2.12 If G 6∈ F, Kn is a connected graph of order n with k vertices of degree n − 1, then CC(G) ≥ k + 2 ≥ 3. 3 Graphs with pendant edges In the this section, we will discuss about the connected coalition number of graphs with δ(G) = 1. First we have the following results. Lemma 3.1 For a connected graph G, assume that ψ is a CC(G)-partition. Let x be a pendant vertex and y = support(x). Let A ∈ ψ with y ∈ A. If any two sets C, D ∈ ψ form a connected coalition, then C = A or D = A. Proof. Suppose on contrary that C 6= A and D 6= A. Since C and D form a connected coalition, then C ∪ D is a connected dominating set. If C ∪ D has no neighbor of x, then x is not dominated by C ∪ D. Hence, C and D do not form a connected coalition., which is a contradiction. So, C = A or D = A. Lemma 3.2 Let G = (V, E) be a connected graph with no full vertex and with δ(G) = 1 and CC(G) ≥ 3. Let x be a pendant vertex and y = support(x). Let ψ be a CC(G)partition. If A ∈ ψ with y ∈ A, then for any pendant vertex w ∈ V , it holds that support(w) ∈ A. 6 Proof. Let w be an arbitrary pendant vertex of G. Let z = support(w). If z ∈ A, then we are done. Then, we assume that z 6∈ A. Let B ∈ ψ with z ∈ B. Now, suppose that x 6∈ A. Hence, there is a set X ∈ ψ with x ∈ X. By Lemma 3.1, X and A form a connected coalition. Since z ∈ B, based on Lemma 3.1, the sets X and A do not form a connected coalition, which is a contradiction Then, we have x ∈ A. Since z ∈ B, based on Lemma 3.1, for any two sets C, D ∈ ψ forming a connected coalition, we have C = B or D = B, also by Lemma 3.1, since y ∈ A, C = A or D = A. Hence, we easily conclude that CC(G) = 2, which is a contradiction, since we assumed that CC(G) ≥ 3. Thus, we must have z ∈ A. We recall the definition of corona product of graphs. The corona product of two graphs H1 and H2 , denoted by H1 ◦ H2 , is defined as the graph obtained by taking one copy of H1 and |V (H1 )| copies of H2 and joining the i-th vertex of H1 to every vertex in the i-th copy of H2 . In the following, we compute the connected coalition number of connected graphs of the form H ◦ K1 . To aid our discussion, we state and prove the following theorem. Theorem 3.3 If G is a connected graph of the form H ◦ K1 , then CC(G) = 2. Proof. Let ψ={V1 , V2 ,. . . , Vk } be a CC(G)-partition of G. By Theorem 2.6, we have CC(G) ≥ 2. It suffices to prove that CC(G) ≤ 2. Suppose on the contrary that CC(G) ≥ 3. Let x be a pendant vertex and y = support(x). Let ψ be a CC(G)partition. Let A ∈ ψ with y ∈ A. Then, by Lemma 3.2, for any pendant vertex w ∈ V , it holds that support(w) ∈ A. Hence, all vertices v of G with deg(v) ≥ 2 lie in A. Then, A is a connected dominating set of G, which is a contradiction. Hence, CC(G) ≤ 2, and since CC(G) ≥ 2, we have CC(G) = 2. We close this section with the following result. Theorem 3.4 If G is a connected graph of order n with δ(G) = 1 and with no full vertex, then CC(G) < n. Proof. Let ψ be a CC(G)-partition and v be a pendant vertex of G and u be the support vertex of v. Suppose on the contrary that CC(G) = n. So, it must be the case that ψ is a singleton partition such that every set Vi , for 1 ≤ i ≤ n, contains a single vertex. Then, {v} ∈ ψ and {u} ∈ ψ. If v and u form a connected coalition, since v is a single vertex of degree one and the only neighbor of v is the vertex u, so u is adjacent to all remaining vertices, it follows that u is a full vertex, a contradiction. Next assume that v and u do not form a connected coalition. Consequently, every singleton set Vi , for 1 ≤ i ≤ n, must contain a full vertex, and it is a contradiction. Hence, CC(G) < n. 4 Trees In this section, we determine the connected coalition trees. First we have the following theorem. 7 Theorem 4.1 For any tree T of order n with no full vertex, we have CC(T ) = 2. Proof. By Theorem 2.6, we have CC(T ) ≥ 2. It suffices to prove that CC(T ) ≤ 2. Suppose on the contrary that CC(T ) ≥ 3. Now we may assume that a and b are two vertices of T such that a is a leaf and b is a support vertex of a. Let ψ be a CC(T )partition, and suppose that V1 ∈ ψ with b ∈ V1 . Since CC(T ) ≥ 3, without loss of generality, assume that V2 , V3 ∈ ψ are two distinct sets such that V2 6= V1 and V3 6= V1 . By Lemma 3.1, each of V2 and V3 form a connected coalition with V1 , however, V2 and V3 do not form a connected coalition. Now, we consider the following cases. • T [V1 ] is connected. By Definition 2.2, V1 is not a dominating set. Then, there exists a vertex u 6∈ V1 with no neighbor in V1 . Hence, if any set A ∈ ψ is in connected coalition with V1 , then A ∩ N [u] 6= ∅. Assume w.l.o.g. that u ∈ V3 . Let u1 ∈ N (u) and assume w.l.o.g. u1 ∈ V2 . Since T [V1 ∪ V2 ] is connected, there is a path Pu1 x between u1 and x for some vertex x ∈ V1 . Note that all vertices on Pu1 x are inside V1 ∪ V2 . Also, since T [V1 ∪ V3 ] is connected, there is a path Qyu between y and u for some vertex y ∈ V1 . Note that all vertices on Qyu are inside V1 ∪ V3 (see Figure 2). Since T [V1 ] is connected, there is a path Rxy between x and y inside V1 . Since u1 ∈ N (u), there is a cycle uu1 Pu1 x Rxy Qyu in T , which is a contradiction. v2 V2 x V1 y u V3 u1 Figure 2: The case that T [V1 ] is connected. • T [V1 ] is not connected. Assume that x, y ∈ V1 such that there is no path between them in G[V1 ]. Since G[V1 ∪V2 ] is connected, there is a path Px,y between x and y that lies in G[V1 ∪ V2 ]. Also, since G[V1 ∪ V3 ] is connected, there is a path Qx,y between x and y that lies in G[V1 ∪ V3 ]. Hence, it is clear that there are two paths between x and y in T , which is a contradiction. As an immediate consequence of Theorem 4.1, we have the following result for the paths. Corollary 4.2 For any path Pn of order n, where n 6= 3, we have CC(Pn ) = 2. 8 u1  1 1  0 E = 0  1 1 1 1 1 0 0 1 1 1 1 1 0 0 0 1 1 1 1 0 0 0 1 1 1 1 1 0  0  1  1 1 u3 u6 u5 Figure 3: The edge-dominated matrix E for C6 . 5 u2  u4 Figure 4: C6 . Graphs G with CC(G) = n and CC(G) = n − 1 For a given graph G, computing CC(G) seems to be an NP-hard problem, and therefore, computing CC(G) for a class of graphs in polynomial time seems to be interesting. In this section, we present two polynomial-time algorithms that for a given connected graph G of order n determine whether it holds CC(G) = n or CC(G) = n − 1. For the sake of simplicity, we assume that G has no full vertex. 5.1 Graphs with CC(G) = n Let epq be an edge of G with two end vertices p and q. A vertex x ∈ V is called edge-dominated by the edge epq , if x is adjacent to p or q. Now, we define the edgedomination matrix Em×n with m rows and n columns on the graph G, where m is number of the edges of G. The definition is as follows. 1 if the vertex x is edge-dominated by the edge epq , E(epq , x) = 0 otherwise. For example, the matrix E depicted in Figure 3 is the edge-dominated matrix of the graph C6 depicted in Figure 4. A useful matrix in Graph Theory, is the incidence matrix. For the graph G, the incidence matrix VEn×m with m rows and n columns is defined as follows. 1 if the vertex x is incident to the edge e, VE(x, e) = 0 otherwise. Now, we prove the following theorem. Theorem 5.1 For any connected graph G of order n and with no full vertex, CC(G) = n if and only if for any vertex x ∈ V , there is an edge e with VE(x, e) = 1 such that X E(e, v) = n. v∈V Proof. Let V = {v1 , . . . , vn } be the vertices of G. Suppose that CC(G) = n. Then, there is a CC(G)-partition ψ = {{v1 }, . . . , {vn }} such that any {vi } forms a connected coalition with some set {vj } with j 6= i. Let x ∈ V be an arbitrary vertex. Since 9 {x} ∈ ψ, there is a vertex u ∈ V such that {u} ∈ ψ forms a connected coalition with {x}. By the definition, {x, u} is a connected dominating set. Then, e = (x, u) is an edge of G, and all vertices of G is dominated P by {x, u}. Therefore, VE(x, e) = 1 and E(e, v) = 1 for any vertex v ∈ V . Hence, v∈V E(e, v) = n. The proof of the converse, is straightforward. Now, we will describe the algorithm. The algorithm first computes the matrices E and VE for the graph G. Then, for all vertices x ∈ V the following operations is applied. P For all edges e, the algorithm checks whether VE(x, e) = 1. If VE(x, e) = 1 and v∈V E(e, v) = n, then we consider f = 1, and the algorithm checks another vertex of V . In the algorithm, we used two variables f and f lag to determine which vertices satisfy the conditions of Theorem 5.1. For more details, see Algorithm 1. Algorithm 1: CheckCCGn(G, V, E) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 input: A connected graph G with no full vertex, and with vertex set V and the edge set E. Computes the martices E and VE; f = 0; s := 0; foreach x ∈ V do foreach e ∈ E do if VE(x, e) == 1 then foreach v ∈ V do s = s + E(e, v); end if s == n then f = 1; break; end end end if f = 0 then f lag := 0; break; end else f lag := 1; f = 0; end end if f lag = 1 then return yes; end else return no; end Now, we compute the time complexity of algorithm CheckCCGn(G, V, E). It is clear that the computations of the matrices E and VE take O(mn) times. Then, since we have three foreach loops, then according to the algorithm, the overall running time of three loops is O(n2 m). Hence, the overall running time of the algorithm is O(n2 m) + O(nm) = O(n2 m). Since m ∈ O(n2 ), then the time complexity of the algorithm is O(n4 ). Hence, we have the following theorem. 10 Theorem 5.2 The worst-case time complexity of algorithm CheckCCGn(G, V, E) is O(n4 ). 5.2 Graphs with CC(G) = n − 1 Let p = (a, b, c) be a triple of vertices a, b and c. A vertex x ∈ V is called three-vertexdominated by p, if x is dominated by {a, b, c}. Now, we define three-vertex-dominated matrix H as follows. 1 if the vertex x is dominated by {a, b, c}, H ({a, b, c}, x) = 0 otherwise. Now, we prove the following theorem. Theorem 5.3 For any connected graph G of order n and with no full vertex, CC(G) = n−1 if and only if there are two vertices u, v ∈ V such that for any vertex x ∈ V \{u, v}, 1. P there is an edge e = (p, q) with p, q 6∈ {u, v} and VE(x, e) = 1 such that v∈V E(e, v) = n, or P 2. G[x, u, v] is connected and w∈V H({x, u, v}, w) = n, and there is a vertex y ∈ V \{u, v} such that G[y, u, v] is connected and X H({y, u, v}, w) = n. w∈V Proof. Let V = {v1 , . . . , vn } be the vertices of G. Suppose that CC(G) = n−1. Then, there is a CC(G)-partition ψ = {{w1 }, . . . , {wn−2 }, {u, v}}. Let C ∈ ψ be an arbitrary set. Suppose that C = {x} is singleton. If C forms a connected coalition with a set {a} ∈ ψ, then by the definition, {x, a} is a connected dominating set. Then, e = (x, a) is an edge of G, and all vertices of G is dominated by {x, a}. Therefore, VE(x, e) = 1 P and E(e, v) = 1 for any vertex v ∈ V . Hence, v∈V E(e, v) = n. Now, if C forms a connected coalition with the set {u, v} ∈ ψ, then by the definition, {x, u, v} is a connected P dominating set. Therefore, G[x, u, v] is connected, and w∈V H({x, u, v}, w) = n. Now, suppose that C = {u, v}. Then, there is a vertex {y} ∈ ψ that forms a connected coalition with C. Therefore, by the P definition, {y, u, v} is a connected dominating set. Then, G[y, u, v] is connected, and w∈V H({y, u, v}, w) = n. The proof of the converse, is straightforward. Now, our second algorithm depicted in Algorithm 2. The algorithm based on Theorem 5.3. It is not hard to see that algorithm CheckCCG2(G, V, E) has four foreach loops and two summations. Then, the overall running time of the algorithm is O(n6 ). Now, we have the following result. Theorem 5.4 The worst-case time complexity of algorithm CheckCCG2(G, V, E) is O(n6 ). 11 Algorithm 2: CheckCCG2(G, V, E) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 6 input: A connected graph G with no full vertex, and with vertex set V and the edge set E. Computes the martices H, E, and VE; f = 0; s := 0; foreach u ∈ V do foreach v ∈ V with u 6= v do foreach x ∈ V \{u, v} do foreach e ∈ E with VE(x, e) = 1 doP P if G[{x, u, v}] is connected and w∈V H({x, u, v}, w) = n, or w∈V E(e, w) = n then f = 1; break; end end if f = 0 then f lag := 0; break; end else f lag = 1; f = 0; end end if f lag = 1 then return yes; end end if f lag = 1 then return yes; end end if f lag = 1 then return yes; end else return no; end Conclusion and future works In this paper, we have introduced the connected coalition concept in graphs and we have studied some properties for the connected coalition number. We characterized all graphs whose have a connected coalition partition. We have shown that for any graph G with δ(G) = 1 and with no full vertex, CC(G) ≤ n − 1. Also we proved that for any tree T , CC(T ) = 2. Finally, we have presented two polynomial-time algorithms that for a given connected graph G of order n determine whether CC(G) = n or CC(G) = n−1. There are many open problems in the study of the connected coalition number of a graph that we state and close the paper with some of them. 1. What is the connected coalition number of graph operations, such as corona, Cartesian, join, lexicographic, and so on? 2. What is the connected coalition number of natural and fractional powers of a 12 graph (see e.g. [3])? 3. What is the effects on CC(G) when G is modified by operations on vertex and edge of G? 4. Similar to the coalition graph of G, it is natural to define and study the connected coalition graph of G for connected coalition partition π, which can be denoted by CCG(G, π), and is defined as follows. Corresponding to any connected coalition partition π = {V1 , V2 , . . . , Vk } in a graph G, a connected coalition graph CCG(G, π) is associated in which there is a one-to-one correspondence between the vertices of CCG(G, π) and the sets V1 , V2 , ..., Vk of π, and two vertices of CCG(G, π) are adjacent if and only if their corresponding sets in π form a connected coalition. Acknowledgement. The work of Hamidreza Golmohammadi is supported by the Mathematical Center in Akademgorodok, under agreement No. 075-15-2022-282 with the Ministry of Science and High Education of the Russian Federation. References [1] S. Alikhani, D. Bakhshesh, H.R. Golmohammadi, Total coalitions in graphs. Available in https://arxiv.org/abs/2211.11590. [2] S. Alikhani, H.R. Golmohammadi, E.V. Konstantinova Coalition of cubic graphs of order at most 10 https://https://arxiv.org/pdf/2212.10004.pdf [3] S. Alikhani, S. Soltani, Distinguishing number and distinguishing index of natural and fractional powers of graphs, Bull. Iranian Math. Soc. 43 (7) (2017) 2471-2482. [4] D. Bakhshesh, M.A. Henning, D. Pradhan, On the coalition number of trees, available at https://arxiv.org/abs/2111.08945. [5] E.J. Cockayne, S. T. Hedetniemi, Towards a theory of domination in graphs. Networks, 7:247-261, 1977. [6] D.-Z. Du, P.-J. Wan, Connected Dominating Set: Theory and Applications. Springer, New York (2013) [7] B.L. Hartnell and D.F. Rall, Connected domatic number in planar graphs. Czechoslovak Math. J. 51(1) (2001) 173–179. [8] 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 (2) (2020), 653–659. [9] 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. (to appear). 13 [10] T.W. Haynes, J.T. Hedetniemi, S.T. Hedetniemi, A.A. McRae and R. Mohan, Upper bounds on the coalition number, Austral. J. Combin. 80 (3) (2021), 442–453. [11] T.W. Haynes, S.T. Hedetniemi, M.A.Henning (eds.): Topics in Domination in Graphs. Developments in Mathematics, vol. 64. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-51117-3 [12] T.W. Haynes, S.T. Hedetniemi, P.J. Slater, Fundamentals of Domination in Graphs, in: Chapman and Hall/CRC Pure and Applied Mathematics Series, Marcel Dekker, Inc. New York, 1998. [13] T.W. Haynes, S.T. Hedetniemi, P.J. Slater, Domination in Graphs, Advanced Topics, Marcel Dekker, Inc., New York, 1998. [14] E. Sampathkumar, H.B. Walikar, The connected domination number of a graph, J. Math. Phys. Sci. 13 (1979) 607–613. [15] B. Zelinka, Domatic number and degrees of vertices of a graph. Math. Slovaca 33 (1983): 145–147. [16] B. Zelinka, On domatic numbers of graphs. Math. Slovaca 31 (1981), 91–95. [17] B. Zelinka: Connected domatic number of a graph. Math. Slovaca 36 (1986), 387–392 14