Doost Ali Mojdeh, Mohammad Reza Samadzadeh

Department of Mathematics, Faculty of Mathematical Sciences, University of Mazandaran, Babolsar, Iran

damojdeh@umz.ac.ir, m.samadzadeh02@umail.umz.ac.ir

A perfect dominating set in a graph G = (V, E) is a subset S ⊆ V such that each vertex in V \ S has exactly one neighbor in S. A perfect coalition in G consists of two disjoint sets of vertices V¹ and V² such that i) neither V¹ nor V² is a dominating set, ii) each vertex in V (G) \ V¹ has at most one neighbor in V¹ and each vertex in V (G) \ V² has at most one neighbor in V2, and iii) V¹ ∪ V² is a perfect dominating set. A perfect coalition partition (abbreviated prc-partition) in a graph G is a vertex partition π = {V1, V2, . . . , Vk} such that for each set Vⁱ of π, either Vⁱ is a singleton dominating set or there exists a set V^j ∈ π that forms a perfect coalition with Vⁱ . In this paper, we initiate the study of perfect coalition partitions in graphs. We obtain a bound on the number of perfect coalitions involving each member of a perfect coalition partition, in terms of maximum degree. The perfect coalition of some special graphs are investigated. Graphs with minimum degree one, triangle-free graphs and trees with large perfect coalition numbers are investigated.

Keywords: perfect coalition, perfect coalition partition, perfect coalition number

Mathematics Subject Classification : 05C69

DOI: 10.5614/ejgta.2025.13.2.8

1. Introduction

Let G = (V, E) denote a simple, finite and undirected graph of order n with vertex set V = V (G) and edge set E = E(G). The open neighborhood of a vertex v ∈ V is the set N(v) = {u : uv ∈ E}, and its closed neighborhood is the set N[v] = N(v)∪{v}. Each vertex of N(v) is called a neighbor of v, and the cardinality of N(v) is called the degree of v, denoted by deg(v) or degG(v).

Received: 13 October 2024, Revised: 13 July 2025, Accepted: 3 August 2025.

A vertex v of degree 1 is called a pendant vertex or leaf, and its neighbor is called a support vertex. The minimum and the maximum degree of G is denoted by δ(G) and ∆(G), respectively. For a set S of vertices of G, the subgraph induced by S is denoted by G[S]. For two sets X and Y of vertices, let [X, Y ] denote the set of edges between X and Y . If every vertex of X is adjacent to every vertex of Y , we say that [X, Y ] is full, while if there are no edges between them, we say that [X, Y ] is empty. A subset Vⁱ ⊆ V is called a singleton set, doubleton set and tripleton set, if |Vi | = 1, |Vⁱ | = 2 and |Vⁱ | = 3, respectively. We denote the path, cycle and complete graph of order n, by Pn, Cⁿ and Kn, respectively. The girth of a graph G, denoted by g(G), is the length of its shortest cycle. A graph is called triangle-free if it has no K³ as a subgraph.

A set S ⊆ V in a graph G = (V, E) is called a dominating set if for any vertex v ∈ V , either v ∈ S or v has a neighbor in S. The minimum cardinality of a dominating set of G is called domination number of G, denoted by γ(G). A set S ⊆ V is a perfect dominating set of a graph G = (V, E) if every vertex in V \ S has exactly one neighbor in S. We denote the minimum cardinality of of a perfect dominating set of G, by γp(G). The concept of domination and its variants have been widely studied in the literature, see for example [7, 8].

In 2020, Haynes et al. [4] introduced the concept of coalition domination in graphs. A coalition in a graph G = (V, E) consists of two disjoint sets V¹ and V² of vertices such that neither V¹ nor V² is a dominating set, but the union V¹ ∪ V² is a dominating set of G. A coalition partition (abbreviated c-partition) in a graph G is a vertex partition π = {V1, V2, . . . , Vk} such that every set Vⁱ either is a singleton dominating set, or is not a dominating set but forms a coalition with another set V^j in G. The maximum cardinality of a coalition partition in G is called the coalition number of G, denoted by C(G). A c-partition of G with order C(G) is called a C(G)-partition. For more studies in this area, we refer the reader to [3, 4, 5, 6]. Since the introduction of this concept, some of its variants have been introduced and studied, see for example [1, 2, 9, 10, 11, 12]. In this paper, we introduce the concepts of perfect coalition and perfect coalition partition in graphs. We define these terms as follows.

Definition 1.1. A perfect coalition in a graph G consists of two disjoint sets of vertices V¹ and V² such that

• (i) Neither V¹ nor V² is a dominating set of G.
• (ii) Each vertex in V (G) \ V¹ has at most one neighbor in V1, and each vertex in V (G) \ V² has at most one neighbor in V2.
• (iii) V¹ ∪ V² is a perfect dominating set of G.

Definition 1.2. A perfect coalition partition (abbreviated prc-partition) in a graph G is a vertex partition π = {V1, V2, . . . , Vk} such that for each set Vⁱ of π either Vⁱ is a singleton dominating set, or there exists a set V^j ∈ π that forms a perfect coalition with Vⁱ . The maximum cardinality of a prc-partition in G is called the perfect coalition number of G, denoted by P RC(G). We say that P RC(G) = 0 if G has no prc-partition. A prc-partition of G with order P RC(G) is called a P RC(G)-partition.

As will be seen below, Section 2 investigates the number of prc-partners of a set in a prc-partition of a graph in terms of maximum degree. In Section 3, we determine perfect coalition number of paths and cycles. In Section 4, we characterize the graphs G with \(\delta(G)=1\) and PRC(G)=|V(G)| in Subsection 4.1, while in Subsection 4.2, we characterize triangle-free graphs G with perfect coalition number |V(G)|. The trees T of order n are characterized whenever \(PRC(T) \in \{n, n-1, n-2\}\) in Subsection 4.3. Finally, we close the paper with some research problems in Section 5.

2. Bounds

Obviously, every prc-partition of a graph G is a c-partition of G. Thus, we have the following.

Observation 2.1. For any graph G, \(PRC(G) \leq C(G)\).

Haynes et al. [4] proved the following result.

Theorem 2.1. [4] Let G be a graph with maximum degree \(\Delta(G)\), and let \(\pi\) be a C(G)-partition. If \(X \in \pi\), then X is in at most \(\Delta(G) + 1\) coalitions.

The following theorem shows that for a graph G, the above upper bound can be reduced to \(\Delta(G)\), when dealing with perfect coalition partitions.

Theorem 2.2. Let G be a connected graph with maximum degree \(\Delta(G)\), and let \(\pi\) be a propartition of G. If \(A \in \pi\), then A is in at most \(\Delta(G)\) perfect coalitions. Further, this bound is sharp.

Proof. If A is a singleton dominating set, then it has no prc-partner. Hence, we may assume that A does not dominate G. Let x be a vertex that is not dominated by A. Now x must be dominated by every prc-partner of A, implying that every prc-partner of A must contain a vertex in N[x]. Since \(|N[x]| \leq \Delta(G) + 1\), it follows that A cannot have more that \(\Delta(G) + 1\) prc-partners. Now we show that A has at most \(\Delta(G)\) prc-partners. Suppose, to the contrary, that A admits \(\Delta(G) + 1\) prc-partners. Let \(V_1, V_2, \ldots, V_{\Delta(G)+1}\) be prc-partners of A. Define G' = G[U], where \(U = \bigcup_{i=1}^{\Delta(G)+1} V_i\). Let X be the set of vertices in G' having a neighbor in A, and Y be the set of vertices \(v_i\) in G' having a neighbor in \(U \setminus V_{v_i}\), where \(V_{v_i}\) is the set in \(\pi\) containing \(v_i\).

First we show that \(X \cap Y = \emptyset\). Suppose, to the contrary, that \(X \cap Y \neq \emptyset\). Let \(s \in X \cap Y\), where \(V_s\) is the set in \(\pi\) containing s. Further, let \(t \in U \setminus V_s\) be a neighbor of s in G, and let \(V_t\) be the set in \(\pi\) containing t. Now we observe that s has at least two neighbors in \(A \cup V_t\), implying that the sets A and \(V_t\) are not prc-partners, a contradiction. Hence, \(X \cap Y = \emptyset\).

Next we show that \(X \cup Y = U\). Suppose, to the contrary, that \(X \cup Y \neq U\). Let \(e \in U \setminus (X \cup Y)\). Let \(V_e\) be the set in \(\pi\) containing e. Now for each \(V_i \in \{V_1, V_2, \dots, V_{\Delta(G)+1}\} \setminus \{V_e\}\), e is not dominated by \(A \cup V_i\), implying that A and \(V_i\) are not prc-partners, a contradiction. Hence, \(X \cup Y = U\).

As before, we let x denote a vertex in G that is not dominated by A. Note that \(N[x] \subseteq U \setminus X = Y\), and so \(Y \neq \emptyset\). Let f be an arbitrary vertex in Y, where \(V_f\) is the set in \(\pi\) containing f. Now for each \(V_i \in \{V_1, V_2, \dots, V_{\Delta(G)+1}\} \setminus \{V_f\}\), since \(V_i \cup A\) is a dominating set of G and A does

not dominate f, it follows that f has a neighbor in Vⁱ . Therefore, degG′(f) ≥ ∆(G), and so deg(f) = degG′(f) = ∆(G). Now, choosing f arbitrarily, we deduce that [Y, V (G) \ Y ] = ∅ which contradicts the fact that G is connected. Hence, A admits at most ∆(G) prc-partners.

To prove the sharpness, for each ∆ ≥ 2, we construct a graph G^∆ with ∆(G∆) = ∆, and a prc-partition π such that there exists a set in π having ∆ prc-partners. Let G^∆ be a graph with V (G∆) = {z, w, v, u1, u2, . . . , u∆}. and E(G∆) = {uiu^j : 1 ≤ i < j ≤ ∆} ∪ {zw, wv, vu1}. Consider the vertex partition π = {{w, z}, {u1, v}, {u2}, {u3}, . . . , {u∆}}. One can observe that π is a prc-partition of G∆, where the set {w, z} forms a perfect coalition with all other sets of π. This completes the proof.

Note that the bound presented in Theorem 2.2 does not hold for disconnected graphs. For example, consider the graph G = K^m ∪ K2, m ≥ 2, with V (G) = {v1, v2, . . . , vm} ∪ {u1, u2} , and E(G) = {viv^j | 1 ≤ i ≤ j ≤ m} ∪ {u1u2}. One can observe that the singleton partition π¹ of G is a prc-partition for G, where the set {u1} has m prc-partners, while ∆(G) = m − 1. Hence we obtain the following result.

Observation 2.2. Let G be a disconnected graph with maximum degree ∆(G), and let π be a prc-partition of G. If A ∈ π, then A is in at most ∆(G) + 1 perfect coalitions. Further, this bound is sharp.

3. Paths and cycles

In this section, we will determine the perfect coalition number of paths and cycles.

Lemma 3.1. [4] For any path Pn, C(Pn) ≤ 6.

Using Lemma 3.1 and Observation 2.1, we have the following.

Corollary 3.1. For any path Pn, P RC(Pn) ≤ 6.

Theorem 3.1. For the path Pn,

\[PRC(P_n) = \begin{cases} 1, & if \ n = 1, \\ 2, & if \ n = 2, \\ 0, & if \ n = 3, \\ 4, & if \ n = 4, 6, 8, \\ 3, & if \ n = 5, \\ 5, & if \ n = 7, 9, 10, 11, 13, \\ 6, & otherwise. \end{cases}\]

Proof. Consider the path Pⁿ with V (Pn) = {v1, v2, . . . , vn} and E(Pn) = {vivi+1 : 1 ≤ i ≤ n − 1}. The result is obvious for n ≤ 4, so we assume n ≥ 5. For the paths P⁵ and P6, it is easy to check that P⁵ has no prc-partition of order 5 or 4, and that P⁶ has no prc-partition of order 6 or 5. Now the partitions {{v1, v5}, {v2}, {v3, v4}} and {{v2}, {v5}, {v3, v6}, {v1, v4}} are prc-partitions for P⁵ and P6, respectively. Therefore, P RC(P5) = 3 and P RC(P6) = 4.

Now let n = 7. By Theorem 2.2, P RC(P7) ̸= 6. On the other hand, the partition set {{v2, v6}, {v1, v7}, {v3}, {v4}, {v5}} is a prc-partition for P7, and so P RC(P7) = 5.

Next assume n = 8. First we show that P RC(P8) ̸= 6. Suppose the opposite is right. By Theorem 2.2, a P RC(P8)-partition consists of two doubleton sets and four singleton sets, where each singleton set forms a perfect coalition with a doubleton set, and each doubleton set forms a perfect coalition with exactly two singleton sets. This contradicts the fact that the vertices v³ and v⁶ are not present in any such perfect coalitions. Hence, P RC(P8) ̸= 6. Now we show that P RC(P8) ̸= 5. Suppose, to the contrary, that P RC(P8) = 5. Let π be a P RC(P8)-partition with 5 sets. By Theorem 2.2, it suffices to examine the following cases.

• π consists of a tripleton set, a doubleton set and three singleton sets.

Since γp(P8) = 3, it follows that each singleton set must form a prc-coalition with a nonsingleton set. Now by Theorem 2.2, there exist two distinct singleton sets in π, say V1,V2, such that V¹ forms a prc-coalition with the doubleton set and V² forms a prc-coalition with the tripleton set. On the other hand, P⁸ has six perfect dominating sets of order 4, namely, N¹ = {v1, v2, v5, v8}, N² = {v1, v4, v5, v8}, N³ = {v1, v4, v7, v8}, N⁴ = {v2, v5, v6, v7}, N⁵ = {v2, v3, v6, v7}, N⁶ = {v2, v3, v4, v7}, and two perfect dominating sets of order 3, namely, T¹ = {v2, v5, v8} and T² = {v1, v4, v7}, where Nⁱ ∩ T^j ̸= ∅, for each 1 ≤ i ≤ 6 and j = 1, 2, a contradiction.

• π consists of three doubleton sets and two singleton sets.

Considering the fact that P⁸ has exactly two perfect dominating sets of order 3, we can easily derive a contradiction. Hence, P RC(P8) ̸= 5.

The partition {{v2, v3, v6}, {v1, v4, v5}, {v7}, {v8}} is a prc-partition for P8, so P RC(P8) = 4. Next assume n = 9. First we show that P RC(P9) ̸= 6. Suppose that the converse is true. By Theorem 2.2, it suffices to examine the following cases.

• π consists of a tripleton set, a doubleton set and four singleton sets.

Since γp(P9) = 3, each singleton set must form a perfect coalition with a non-singleton set. Thus, by Theorem 2.2, each non-singleton set must form a perfect coalition with two singleton sets. But P⁹ has a unique perfect dominating set of order 3, namely {v2, v5, v8}, a contradiction.

• π consists of three doubleton sets and three singleton sets. Similar to the previous case, we can easily derive a contradiction. Hence, P RC(P9) ̸= 6.

On the other hand, the partition {{v3, v6, v9}, {v1, v4, v8}, {v2}, {v5}, {v7}} is a prc-partition for P9, so P RC(P9) = 5.

Next assume n = 10. First we show that P RC(P10) ̸= 6. Suppose that the converse is true. Using Theorem 2.2 and the fact that γp(P10) = 4, we only need to examine the case in which π consists of two sets of order 3 and four singleton sets. In this case, each singleton set must form a perfect coalition with a set of order 3, and that each set of order 3 must form a perfect coalition with exactly two singleton sets. Consequently, there must be four perfect dominating sets (name

A,B,C and D) of P¹⁰ of order 4 such that these sets can be partitioned into two pair, say (A, B) and (C, D), with the property that the sets in each pair have exactly three vertices in common. But P¹⁰ has four perfect dominating sets of order 4, namely V¹ = {v1, v4, v7, v10}, V² = {v2, v3, v6, v9}, V³ = {v2, v5, v6, v9} and V⁴ = {v2, v5, v8, v9}, where V¹ has no common vertex with any other sets, a contradiction. The partition {{v1, v7}, {v4, v10}, {v2, v9}, {v3, v6}, {v5, v8}} is a prc-partition for P10, so P RC(P10) = 5.

Next assume n = 11. Using Theorem 2.2, the fact that γp(P11) = 4 and the fact that P¹¹ has exactly two perfect dominating sets of order 4, namely {v1, v4, v7, v10} and {v2, v5, v8, v11}, it is not hard to see that, P RC(P11) ̸= 6.

Now the partition {{v1, v4, v8, v11}, {v2, v3, v6, v10}, {v5}, {v7}, {v9}} is a prc-partition for P11, so P RC(P11) = 5.

Next assume n = 13. The partition {{v1, v4, v5, v8, v12}, {v2, v3, v7, v10, v13}, {v6}, {v9}, {v11}} is a prc-partition for P13, so P RC(P13) ≥ 5. Now we show that P RC(P13) ̸= 6. Suppose that the converse is true. Let π be a P RC(P13)-partition. Note that P¹³ has five perfect dominating sets of order 5, namely, S¹ = {v1, v4, v7, v10, v13}, S² = {v2, v3, v6, v9, v12}, S³ = {v2, v5, v6, v9, v12}, S⁴ = {v2, v5, v8, v9, v12}, S⁵ = {v2, v5, v8, v11, v12}, and twenty perfect dominating sets of order 6, namely,

M1 = {v1, v2, v5, v6, v9, v12}, M2 = {v2, v3, v6, v7, v10, v13}, M3 = {v1, v2, v5, v8, v9, v12},
M4 = {v2, v3, v6, v9, v10, v13}, M5 = {v1, v2, v5, v8, v11, v12}, M6 = {v2, v3, v6, v9, v12, v13},
M7 = {v1, v4, v5, v8, v9, v12}, M8 = {v2, v3, v6, v9, v12, v13}, M9 = {v1, v4, v5, v8, v11, v12},
M10 = {v2, v3, v6, v9, v12, v13}, M11 = {v1, v4, v7, v8, v11, v12}, M12 = {v2, v5, v8, v9, v12, v13},
M13 = {v1, v2, v3, v6, v9, v12}, M14 = {v2, v3, v4, v7, v10, v13}, M15 = {v1, v4, v5, v6, v9, v12},
M16 = {v2, v5, v6, v7, v10, v13}, M17 = {v1, v4, v7, v8, v9, v12}, M18 = {v2, v5, v8, v9, v10, v13},
M19 = {v1, v4, v7, v10, v11, v12}, M20 = {v2, v5, v8, v11, v12, v13}.

Observe that for each 1 ≤ i ≤ 5 and 1 ≤ j ≤ 20, Sⁱ ∩ M^j ̸= ∅. Now using Theorem 2.2, and the fact that γp(P13) = 5, the only non-trivial cases to examine are as follows.

• π consists of a set of order 5, a set of order 4 and four singleton sets.
  • By Theorem 2.2, each singleton set must form a prc-coalition with exactly one non-singleton set, and each non-singleton set must form a prc-coalition with exactly two singleton sets. Thus, P¹³ must contain two perfect dominating sets A and B, such that |A| = 5, |B| = 6 and A ∩ B = ∅, a contradiction.
• π consists of two sets of order 4, a doubleton set and three singleton sets. An argument similar to the one used in previous case indicates that this case is also impossible.
• π consists of a set of order 4, a tripleton set, two doubleton sets and two singleton sets. Considering Theorem 2.2, and the fact that γp(P13) = 5, we deduce that each singleton set must form a prc-coalition with the set of order 4, and each doubleton set must form a prc-coalition with the set of order 3. This implies that P¹³ contains four perfect dominating sets (name A,B,C and D) of order 5 such that A ∩ B = ∅, and C ∩ D = ∅ which is a

contradiction since for each 2 ≤ i ≤ j ≤ 5, we have Sⁱ ∩ S^j ̸= ∅. Hence, P RC(P13) ̸= 6, and so P RC(P13) = 5.

If n ≥ 12, and n ≡ 0 (mod 2), then the partition{V¹ = {v2, v6, v9} ∪ {v4^k : k ≥ 3} ∪ {v4k+1 : k ≥ 3}, V² = {v1, v4, v7} ∪ {v4k−¹ : k ≥ 3} ∪ {v4k+2 : k ≥ 3}, V³ = {v5}, V⁴ = {v3}, V⁵ = {v10}, V⁶ = {v8}} is a prc-partition of order 6 for Pn.

Finally, if n ≥ 15, and n ≡ 1 (mod 2), then the partition {V¹ = {v2, v9, v12} ∪ {v4k−¹ : k ≥ 4} ∪ {v4^k : k ≥ 4}, V² = {v1, v4, v7, v10} ∪ {v4k−² : k ≥ 4} ∪ {v4k+1 : k ≥ 4}, V³ = {v5, v8}, V⁴ = {v3, v6}, V⁵ = {V13}, V⁶ = {v11}} is a prc-partition of order 6 for Pn. Thus the proof is observed.

Lemma 3.2. [4] For any cycle Cn, C(Cn) ≤ 6.

Using Lemma 3.2 and Observation 2.1, we have the following.

Corollary 3.2. For any cycle Cn, P RC(Cn) ≤ 6.

Lemma 3.3. If n ≥ 9 and n ̸= 11, then P RC(Cn) = 6.

Proof. Consider the cycle Cⁿ with V (Cn) = {v1, v2, . . . , vn} and E(Cn) = {vivi+1 : 1 ≤ i ≤ n − 1} ∪ {v1vn}. The partitions

π⁹ = {{v1, v7}, {v2, v8}, {v3, v9}, {v4}, {v5}, {v6}},

π¹² = {{v1, v7}, {v2, v8}, {v3, v9}, {v4, v10}, {v5, v11}, {v6, v12}} and

π¹⁵ = {{v1, v7, v13}, {v2, v8, v14}, {v3, v9, v15}, {v4, v10}, {v5, v11}, {v6, v12}}

are prc-partitions for C9, C¹² and C15, respectively. Thus, using Corollary 3.2, we have P RC(C9) = P RC(C12) = P RC(C15) = 6. Now let π = {V1, V2, . . . , V6} be a prc-partition for Cn. We say that π is proper, if it has the following properties.

• (i) V² and V³ are prc-partners of V1.
• (ii) V⁵ and V⁶ are prc-partners of V4.
• (iii) v¹ ∈ V¹ and vⁿ ∈ V4.

To complete the proof, we show that if n ≥ 10 and n ̸= 11, 12, 15, then Cⁿ has a proper prcpartition. We proceed by induction on n. Consider the partitions

\[\pi_{10} = \{V_1 = \{v_1, v_5, v_8\}, V_2 = \{v_4\}, V_3 = \{v_2\}, V_4 = \{v_3, v_6, v_{10}\}, V_5 = \{v_7\}, V_6 = \{v_9\}\},\] \[\pi_{13} = \{V_1 = \{v_1, v_5, v_8, v_{11}\}, V_2 = \{v_2\}, V_3 = \{v_4\}, V_4 = \{v_3, v_6, v_{13}\}, V_5 = \{v_9, v_{12}\}, V_6 = \{v_7, v_{10}\}\},\]

π¹⁶ = {V¹ = {v1, v5, v8, v11, v14}, V² = {v4}, V³ = {v2, }, V⁴ = {v3, v6, v16}, V⁵ = {v9, v12, v15}, V⁶ = {v7, v10, v13}} and

π¹⁹ = {V¹ = {v1, v8, v11, v14, v17}, V² = {v4, v7}, V³ = {v2, v5}, V⁴ = {v3, v6, v9, v19}, V⁵ = {v12, v15, v18}, V⁶ = {v10, v13, v16}}.

These partitions are respectively, proper prc-partitions for C10, C13, C¹⁶ and C19. This establishes the base case. Now assume that π = {V1, V2, . . . , V6} is a proper prc-partition for Ck. Consider the partition π ′ = {V¹ ∪ {vk+1, vk+2}, V2, V3, V⁴ ∪ {vk+3, vk+4}, V5, V6}. One can observe that π ′ is a proper prc-partition for Ck+4. This completes the proof.

Theorem 3.2. For the cycle Cn,

\[PRC(C_n) = \begin{cases} n, & if \ n = 3, 4, 6, \\ 3, & if \ n = 5, \\ 4, & if \ n = 8, \\ 5, & if \ n = 7, 11, \\ 6, & otherwise. \end{cases}\]

Proof. Consider the cycle Cⁿ with V (Cn) = {v1, v2, . . . , vn} and E(Cn) = {vivi+1 : 1 ≤ i ≤ n − 1} ∪ {v1vn}. The result is obvious for n ∈ {3, 4, 6}. Now let n = 5. Note that the singleton vertex partition of C⁵ is not a prc-partition for C5, so P RC(C5) ̸= 5. Note also that since C⁵ has no perfect dominating set of order 2, it follows from Theorem 2.2 that P RC(C5) ̸= 4. The partition {{v1}, {v2, v3}, {v4, v5}} is a prc-partition for C5, so P RC(C5) = 3.

Next assume n = 7. Considering Theorem 2.2 and γp(C7) = 3, we deduce that P RC(C7) ̸= 6. Now we show that P RC(C7) = 5. Let π = {V1, V2, V3, V4, V5} where V¹ = {v1, v7}, V² = {v2, v6}, V³ = {v3}, V⁴ = {v4}, V⁵ = {v5}. Then π is a prc-partition for C7.

Next assume n = 8. Considering Theorem 2.2 and γp(C8) = 4, it is not difficult to see that P RC(C8) ̸= 6, and that P RC(C8) ̸= 5. The partition {{v1, v2, v5}, {v6}, {v3, v4, v7}, {v8}} is a prc-partition for C8, so P RC(C8) = 4.

Next assume n = 11. Considering Theorem 2.2 and γp(C11) = 5, it is not difficult to see that P RC(C11) ̸= 6. The partition {{v1, v4, v8, v11}, {v2, v3, v6, v10}, {v5}, {v9}, {v7}} is a prcpartition for C11, so P RC(C11) = 5.

Finally, applying Lemma 3.3, the desired result follows.

4. Graphs with large perfect coalition number

Our aim in this section is to characterize graphs with large perfect coalition number in some families of graphs. The following observation characterizes disconnected graphs with maximum perfect coalition number.

Observation 4.1. Let G be a disconnected graph of order n. Then P RC(G) = n if and only if G ≃ K^s ∪ Kr, for some positive integers r, s ≥ 1.

4.1. Graphs G with δ(G) = 1 and P RC(G) = |V (G)|

In this subsection, we characterize graphs with minimum degree one and with maximum perfect coalition number. For this purpose, we define the family of graphs B as follows.

Definition 4.1. Let G be a graph with δ(G) = 1. Let x be a leaf of G and let y be the support vertex of x. Then G ∈ B, if and only if G has the following properties.

• (i) N(y) is an independent set of G.
• (ii) V (G) \ (N(y) ∪ {x, y}) induces a clique in G.

(iii) [N(y) \ {x}, V(G) \ (N(y) ∪ {x, y})] is full.

Theorem 4.1. Let G be a connected graph of order n with δ(G) = 1. Let x be a leaf of G, and let y be the support vertex of x. Then P RC(G) = n if and only if either G = K2, or G ∈ B.

Proof. Clearly, P RC(K2) = 2. Now assume that G ∈ B. Consider the singleton partition π¹ of G. Observe that for each vertex v ∈ N(y)\ {x}, the set {v} forms a prc-coalition with {y}, and for each vertex v ∈ V (G) \ N(y) ∪ {x, y}, the set {v} forms a prc-coalition with {x}. Hence, π¹ is a prc-partition of G, and so P RC(G) = n. Conversely, assume P RC(G) = n. Let A = N(y)\ {x}, and B = V (G) \ (A ∪ {x, y}). If A = ∅ and B = ∅, then G = K2, as desired. Now assume G ̸= K2. Since G is connected, we have A ̸= ∅. Note also that B ̸= ∅, for otherwise, G would be a star, and so G would have no P RC-partition. Now consider the P RC(G)-partition π1. Since N(x) = {y}, each set in π¹ \ {{x}, {y}} must form a prc-coalition with {x} or {y}, to dominate x. Now for each v ∈ A, the set {v} cannot form a prc-coalition with {x}, since y has more than one neighbors in {v, x}. Thus, {v} forms a prc-coalition with {y}, implying that [A, B] is full. Note also that v has no neighbor in A, for otherwise, {v, y} would not be a perfect dominating set. Therefore, A is an independent set in G. Further, for each u ∈ B, the set {u} must form a prc-coalition with {x}, since {u, y} is not a perfect dominating set. Since [{x}, B] is empty, it follows that B induces a clique in G. Hence, G ∈ B.

4.2. Triangle-free graphs G with P RC(G) = |V (G)|

In this subsection, we characterize all triangle-free graphs with maximum perfect coalition number. For this purpose, we define the families of graphs T¹ and T² as follows.

Definition 4.2. Let T¹ represent the family of bipartite graphs H − M, where H = Kr,r is a complete bipartite graph with r ≥ 2, and M is a perfect matching in H.

Definition 4.3. Let T² represent the family of bipartite graphs H − M, where H = Kr,s is a complete bipartite graph with r, s ≥ 2, and M (possibly empty) is a matching in H such that |M| < min{r, s}.

Figure 1 illustrates some examples of graphs in T¹ ∪ T2, where the vertices involved in M are colored red.

Theorem 4.2. Let G be a triangle-free graph of order n ≥ 4. Then P RC(G) = n if and only if G ∈ T¹ ∪ T2.

Proof. Suppose that G ∈ T¹ ∪ T2. Let K¹ = {v1, v2, . . . , v^|K1^|} and K² = {u1, u2, . . . , u^|K2^|} denote the partite sets of G. First assume G ∈ T1. Assume, without loss of generality, that uivⁱ ∈/ E(G), for each 1 ≤ i ≤ n 2 . Now observe that the singleton partition π¹ of G is a prc-partition for G, where the sets {ui} and {vi} are prc-partners, for each 1 ≤ i ≤ n 2 . Thus, P RC(G) = n. Now assume G ∈ T2. Consider the singleton partition π¹ of G. Further, assume that the vertices v¹ ∈ K¹ and u¹ ∈ K² are not saturated by M. Now for each vⁱ ∈ K1, if degG(vi) = |K2|, then the set {vi} forms a prc-coalition with {u1}, otherwise, {vi} forms a prc-coalition with {uj}, where viu^j ∈/ E(G). By symmetry, we can show that each singleton subset of K² has also a prcpartner in π1. Hence, π¹ is a prc-partition for G, and so P RC(G) = n. Conversely, Assume that P RC(G) = n. We proceed with proving the following claims.

Figure 1: Some graphs in T¹ ∪ T2.

Claim 1. g(G) ≤ 6.

Proof. Suppose to the contrary that, g(G) ≥ 7. Let C be a cycle of G with order g(G). Since C has no perfect dominating set of order 2, it follows that for any vertex v ∈ V (C), the set {v} is not a prc-partner of any set {u} ⊂ V (C), so it must be a prc-partner of a set {u} ⊆ V (G) \ V (C). Thus, {u} dominates V (C) \ Nc[v], implying that G contains triangles, a contradiction.

An argument similar to the one presented above shows that g(G) ̸= 5.

Claim 2. If g(G) = 6, then G = C6.

Proof. Suppose to the contrary that, G ̸= C6. Let C be a cycle of order 6 in G, and let v ∈ V (G) \ V (C). Note that the set {v} cannot form a prc-partition with any set {u} ⊂ V (C), for otherwise, {v} would dominate V (C) \ N[u], and so triangles would be created. Hence, {v} must form a prc-coalition with a set {u} ⊆ V (G) \ V (C). Now since each vertex in V (C) is dominated by {u, v}, we can find a vertex in {u, v} having at least three neighbors in V (C), which creates cycles of order 3 or 4, a contradiction. Hence, G = C6, and so G ∈ T1.

Note also that if G has no cycle, then it follows from Observation 4.1 and Corollary 4.1 that G ∈ T¹ ∪ T2. Hence, for the rest of the proof, we may assume that g(G) = 4. Consider the singleton P RC(G)-partition π1. Let C be a 4-cycle in G with V (C) = {x, y, z, t} and E(C) = {xy, yz, zt, tx}. We distinguish two cases.

Case 1. The set {x} forms a prc-coalition with a singleton subset of V (C).

Observe that {x} cannot form a prc-coalition with {z}, so we may assume, by symmetry, that the sets {x} and {y} are prc-partners. Define A = N(x) \ {t, y} and B = N(y) \ {x, z}. Observe that A ∩ B = ∅. Now we consider the following subcases.

Subcase 1.1. A = ∅ and B = ∅. It follows that G = C4, and so G ∈ T2.

Subcase 1.2. A ̸= ∅ and B = ∅. If [{z}, A] is full, then G ∈ T2, as desired. Hence, we may assume that [{z}, A] is not full. Let v ∈ A such that vz /∈ E(G). Note that the set {v} has no prc-partner in {{x}, {y}, {t}}. Now if A = {v}, then G ∈ T2, as desired. Hence, we may assume A ̸= {v}. Note that [{z}, {A \ {v}] is full, for otherwise {v} would have no prc-partner. Hence, G ∈ T2.

Subcase 1.3. A = ∅ and B ̸= ∅. Similar to the previous subcase, we can show that G ∈ T2.

Subcase 1.4. A ̸= ∅ and B ̸= ∅. Consider arbitrary vertices v ∈ A and u ∈ B. Observe that {v} has no prc-partner in {{t}, {y}}. Now it is not hard to verify that either |[{v}, {x, z} ∪ B]| = |B| + 2, or |[{v}, {x, z} ∪ B]| = |B| + 1. Similarly, we can show that either |[{u}, {y, t} ∪ A]| = |A| + 2, or |[{u}, {y, t} ∪ A]| = |A| + 1. Consequently, G is a bipartite graph with partite sets A ∪ {y, t} and B ∪ {x, z} satisfying all properties of Definition 4.3. Hence, G ∈ T2.

Case 2. The set {x} does not form a prc-coalition with any singleton subset of V (C). Let {e} be a prc-partner of {x}. Define A = N(x) \ {y,t, e} and B = N(e) \ {z, x}. Observe that ez ∈ E(G) and A ∩ B = ∅. We consider the following subcases.

Subcase 2.1. A = ∅ and B = ∅. It is clear that G ∈ T2, as desired.

Subcase 2.2. A = ∅ and B ̸= ∅. Note that the set {y} (or {t}) must form a prc-coalition with either a member of {{x}, {z}}, or a singleton subset of B, implying that either [{y}, B] is full, or |[{y}, B]| = |B| − 1. Now if xe ∈ E(G), then for any subset {u} ⊆ B, the set {u} must have a prc-partner in {{y}, {t}, {e}}, implying that either [{u}, {y, t, e}] is full, or |[{u}, {y, t, e}]| = 2. Otherwise, for any subset {u} ⊆ B, the set {u} must have a prc-partner in {{y}, {t}}, implying again that either [{u}, {y, t, e}] is full, or |[{u}, {y, t, e}]| = 2. Hence, G is a bipartite graph with partite sets {y, t, e} and B ∪ {x, z}, satisfying all properties of Definition 4.3, and so G ∈ T2.

Subcase 2.3. A ̸= ∅ and B = ∅. Note that for any subset {v} ⊆ A, the set {v} must have a prcpartner in {{x}, {z}}, implying that either [{v}, {x, z}] is full, or |[{v}, {x, z}]| = 1. Now if the set {z} has a prc-partner in {{y}, {t}, {e}}, then [{z}, A] is full. Otherwise, {z} must form a prccoalition with a singleton subset in A, implying that either [{z}, A] is full, or |[{z}, A]| = |A| − 1. Note also that the set {y} must have a prc-partner in {{x}, {z}}. Thus, if {z} has no prc-partner in {{y}, {t}, {e}}, then {y} must form a prc-coalition with {x}, implying that xe ∈ E(G), and so [{x}, {y, t, e} ∪ A] is full. Consequently, G is a bipartite graph with partite sets {x, z} and A ∪ {y, t, e}, satisfying all properties of Definition 4.3, and so G ∈ T2.

Subcase 2.4. A ̸= ∅ and B ̸= ∅. Note that for any subset {u} ⊂ B ∪ {z}, the set {u} must form a prc-partner with either a member of {{y}, {t}, {e}}, or a singleton subset of A, implying that either [{u}, A ∪ {y, t, e}] is full, or |[{u}, A ∪ {y, t, e}]| = |A| + 2. Further, for any subset {v} ⊂ A ∪ {y, t}, the set {v} must form a prc-partner with either a member of {{x}, {z}}, or a singleton subset of B, implying that either [{v}, B∪{x, z}] is full, or |[{v}, B∪{x, z}]| = |B|+1. Hence, G is a complete bipartite graph with partite sets K¹ = A ∪ {y, t, e} and K² = B ∪ {x, z} such that each vertex in K¹ has degree either |K2| or |K2| − 1, and each vertex in K² has degree either |K1| or |K1|−1. To complete the proof, we show that if K¹ contains a vertex of degree |K2|, then so does K2, and vice versa. Assume first that K¹ contains a vertex v with deg(v) = |K2|. If v = e, then the desired result follows. Hence, we may assume v ̸= e, implying that xe /∈ E(G). Now the set {v} must form a prc-coalition with {z} or a singleton subset {u} ⊆ B, implying, respectively, that [{z}, A] is full, or [{u}, A ∪ {y, t}] is full, as desired. Conversely, assume K² contains a vertex v with deg(v) = |K1|. If v = x, then the desired result follows. Hence, we may assume v ̸= x, implying that xe /∈ E(G). Now the set {v} must form a prc-coalition with a member of {{y}, {t}}, say {y}, or a singleton subset {u} ⊆ A, implying, respectively, that [{y}, B] is full, or [{u}, B ∪ {z}] is full, as desired. Hence, G ∈ T¹ ∪ T2. This completes the proof.

4.3. Trees with large perfect coalition number

In this subsection, we investigate trees with large perfect coalition number. As an immediate result from Theorem 4.1, we have the following.

Corollary 4.1. Let T be a tree of order n. Then P RC(T) = n if and only if T ∈ {P1, P2, P4}.

We define the tree R as shown below.

Figure 2: The tree R.

Theorem 4.3. If T ̸= P⁴ is a tree of order n > 2, then P RC(T) ≤ n − 2 with equality if and only if T ∈ {P5, P6, P7, R}.

Proof. By Corollary 4.1, P RC(T) ̸= n. Now we prove the following claim.

Claim 1. P RC(T) ̸= n − 1.

Proof. Suppose, to the contrary, that P RC(T) = n − 1. Since stars are the only trees with a full vertex, and stars have no prc-partition, it follows that T has no full vertex. Let π be a P RC(T) partition. Note that π consists of a doubleton set, say {u, v}, and n − 2 singleton sets. Let the set {x} be a prc-partner of {u, v}. Further, let A and B denote the set of vertices in V (T) \ {x, u, v} that are dominated by {x} and {u, v}, respectively. Since {x, u, v} is a perfect dominating set of T, we have A ∩ B = ∅. Also, since {u, v} is not a dominating set, it follows that A ̸= ∅. Now we show that B ̸= ∅. Suppose that the converse is true. Since T is connected, x has a neighbor in {u, v}. If uv ∈ E(T), then it is easy to check that for any set {a} ⊆ A, {a} has no prc-partner. Hence, we may assume that uv /∈ E(T). Now it follows from connectedness of T that [{x}, {u, v}] is full, implying that {x} is a full vertex, a contradiction. Hence, B ̸= ∅. Let {a} be an arbitrary singleton subset of A. Now we consider the following cases.

Case 1. uv ∈ E(T) and [{x}, {u, v}] ̸= ∅.

We may assume, by symmetry, that xv ∈ E(T). Since u is not dominated by {a} ∪ {x}, the sets {a} and {x} are not prc-partners. Further, since x has two neighbors in {a} ∪ {u, v}, the sets {a} and {u, v} are not prc-partners. Note also that for any singleton subset {b} ⊆ B, {a} and {b} are not prc-partners, for otherwise, a cycle or cycles would be created. Hence, {a} has no prc-partner, a contradiction.

Case 2. uv /∈ E(T) and [{x}, {u, v}] ̸= ∅. We divide this case into two subcases. Subcase 2.1. |[{x}, {u, v}]| = 1.

We may assume, by symmetry, that xv ∈ E(T). Since u is not dominated by {a}∪{x}, the sets {a} and {x} are not prc-partners. Further, since x has more than one neighbors in {a} ∪ {u, v}, the sets {a} and {u, v} are not prc-partners. Note also that no singleton subset of B dominates {u, v} implying that no singleton subset of B can form a perfect coalition with {a}. Hence, {a} has no prc-partner, a contradiction.

Subcase 2.2. |[{x}, {u, v}]| = 2.

Since x has more than one neighbors in {a} ∪ {u, v}, the sets {a} and {u, v} are not prcpartners. Further, no singleton subset of B dominates {u, v} implying that no singleton subset of B can form a perfect coalition with {a}. Not also that the sets {a} and {x} are not prc-partners, for otherwise, a cycle or cycles would be created. Hence, {a} has no prc-partner, a contradiction.

Case 3. [{x}, {u, v}] is empty.

Since T is connected, [A, B] ̸= ∅. Let ab ∈ E(T), where b ∈ B. Since u is not dominated by {a} ∪ {x}, the sets {a} and {x} are not prc-partners. Further, since b has more than one neighbors in {a} ∪ {u, v}, the sets {a} and {u, v} are not prc-partners. Note also that no singleton subset of B dominates {u, v} implying that no singleton subset of B can form a perfect coalition with {a}. Hence, {a} has no prc-partner, a contradiction. Hence, P RC(T) ̸= n − 1, and so P RC(T) ≤ n − 2.

Now we prove the second part of the theorem. By Theorem 3.2, P RC(P5) = 3, P RC(P6) = 4 and P RC(P7) = 5. Also, the partition {{v1}, {v2}, {v3, v4}, {v5, v6}} is a prc-partition for R, so P RC(R) = 4. Conversely, assume that P RC(T) = n − 2. Let π be a P RC(T)-partition. Consider two cases.

Case 1. π consists of a tripleton set {u, v, t}, and n − 3 singleton sets.

We show that this case is impossible. Suppose that the converse is true. Let the set {x} be a prc-partner of {u, v, t}. Further, let A and B denote the set of vertices in V (T) \ {x, u, v, t} that are dominated by {x} and {u, v, t}, respectively. Since {x, u, v, t} is a perfect dominating set of T, we have A ∩ B = ∅. Since {u, v, t} is not a dominating set, it follows that A ̸= ∅. Now we show that B ̸= ∅. Suppose that the converse is true. Since T is connected, x has a neighbor in {u, v, t}, implying that for any set {a} ⊆ A, {a} cannot form a prc-coalition with {u, v, t}. Thus, {a} must form a prc-coalition with {x}, implying that [{x}, {u, v, t}] is full. Thus, x is a full vertex, which is a contradiction. Hence, B ̸= ∅. Let {a} and {b} be arbitrary singleton subsets of A and B, respectively. Since b has exactly one neighbor in {u, v, t}, and a has no neighbor in {u, v, t}, it follows that {a} cannot be a prc-partner of {b}. Now we show that the sets {a} and {x} are not prc-partners. Suppose that the converse is true. It follows that [{x}, {u, v, t}] is full, and that ab ∈ E(T). By symmetry, we may assume that bu ∈ E(T). Now observe that the set {x, u, b, a} induces a cycle, a contradiction. It remains to show that {a} cannot form a prc-partition with {u, v, t}. If x has a neighbor in {u, v, t}, then x has more than one neighbors in {a} ∪ {u, v, t}, implying that the sets {a} and {u, v, t} are not prc-partners. Hence, we may assume that [{x}, {u, v, t}] = ∅. Since T is connected, it follows that a has a neighbor in B. Let ab ∈ E(T). Now we observe that b has more that one neighbors in {a} ∪ {u, v, t}. Hence, {a} cannot form a prc-partition with {u, v, t}, and so this case is impossible.

Case 2. π consists of two doubleton sets, say {u, v} and {t, z}, and n − 4 singleton sets. We divide this case into two subcases.

Subcase 2.1. {u, v} and {t, z} are prc-partners.

Let A and B denote the set of vertices in V (T) \ {u, v, t, z} that are dominated by {u, v} and {t, z}, respectively. Since {u, v, t, z} is a perfect dominating set of T, we have A∩B = ∅. Observe that the sets A and B cannot both be empty sets.

Claim 2. If A = ∅, then T = P5.

Proof. Since {t, z} is not a dominating set, there exists a vertex in {u, v}, say u, that has no neighbor in {t, z}. Now since T is connected, it follows that uv ∈ E(T), and that v has a neighbor in {t, z}. Assume, by symmetry that, vt ∈ E(T). Let {b} be an arbitrary singleton subset of B. Since {b} is not a prc-partner of {t, z}, it must form a prc-coalition with {u, v}, implying that tb /∈ E(T), and that [{z}, {u, v}] = ∅. Choosing b arbitrarily, we deduce that t has no neighbor in B, implying that [{z}, B] is full. Now, for T to be connected, we must have tz ∈ E(T). Note also that B = {b}, for otherwise {b} would have no prc-partner. Hence, T = P5.

By symmetry, if B = ∅, then T = P5. For the rest of this subsection, we may assume that A ̸= ∅ and B ̸= ∅. Let {a} and {b} be arbitrary singleton subsets of A and B, respectively. Note that [{u, v}, {t, z}] ̸= ∅, for otherwise, it is easy to verify that the set {a} would not have a prc-partner.

Claim 3. [{t}, {u, v}] is not full.

Proof. Suppose that the converse is true. Assume, by symmetry, au ∈ E(T). Observe that no singleton subset of A can form a prc-coalition with {a}. Since u has more than one neighbors in {a} ∪ {t, z}, the sets {a} and {t, z} are not prc-partners. Further, since t has more than one neighbors in {u, v}, the sets {a} and {u, v} are not prc-partners, and since {a} has exactly one neighbor in {u, v}, no singleton subset of B can form a prc-coalition with {a}. Hence, {a} has no prc-partner, a contradiction.

Therefore, by symmetry, none of the sets [{z}, {u, v}], [{u}, {t, z}] and [{v}, {t, z}] are full.

Claim 4. If |[{u, v}, {t, z}]| = 1, then T = P6.

Proof. Let by symmetry that, [{u, v}, {t, z}] = {vt}. Observe that A = {a} and B = {b}. So, it is not hard to verify that the set {a} can only form a prc-partition with {t, z}, so [{a}, {u, v}] = {au}. By symmetry, [{b}, {t, z}] = {bz}. Further, note that ab /∈ E(T), for otherwise, b would have more than one neighbors in {a}∪{t, z}, contradicting the fact that {a} and {t, z} are prc-partners. Thus, for T to be connected, we must have {uv, tz} ⊂ E(T), and so T = P6.

Finally, we may assume by symmetry that, [{u, v}, {t, z}] = {vt, uz}. Assume by symmetry that, av ∈ E(T). Since v has more that one neighbors in {t, z} ∪ {a}, the sets {t, z} and {a} are not prc-partners. Further, Observe that {a} cannot form a prc-coalition with any singleton subset of B. Hence, {a} must form a prc-coalition with {u, v}, implying that ab ∈ E(T). Thus, bt /∈ E(T), and so bz ∈ E(T). Since |A| = |B| = 1, T = P6.

Subcase 2.2. {u, v} and {t, z} are not prc-partners.

Let {w} be a prc-partner of {u, v}. Let A and B denote the set of vertices in V (T) \ {u, v, w} that are dominated by {w} and {u, v}, respectively. Since {u, v, w} is a perfect dominating set of T, we have A ∩ B = ∅. Also, since the set {u, v} is not dominating sets, it follows that A ̸= ∅. Now we show that B ̸= ∅. Suppose, to the contrary, that B = ∅. Let {a} ⊆ A. Since {w} is not a dominating set, [{w}, {u, v}] is not full. Now since T is connected, it follows that uv ∈ E(T) and

that w has a neighbor in {u, v}. Assume, by symmetry, vw ∈ E(T). Now observe that the set {a} has no prc-partner, a contradiction.

Claim 5. {t, z} ⊈ A.

Proof. Suppose, to the contrary, that {t, z} ⊆ A. Observe that {t, z} cannot form a prc-partition with any singleton subset of A. Also by our assumption, the sets {u, v} and {t, z} are not prcpartners. Further, for any arbitrary singleton subset {b} ⊆ B, since b has one neighbor in {u, v}, it follows that the sets {b} and {t, z} are not prc-partners. Note also that {t, z} does not form a prc-partition with {w}, for otherwise, a cycle or cycles would be created. Hence, the set {t, z} has no prc-partner, a contradiction.

Claim 6. |A| ≤ 2.

Proof. Suppose, to the contrary, that |A| ≥ 3. Let {a, c, d} ⊆ A such that a /∈ {t, z}. Assume first that [{w}, {u, v}] is full. Observe that the set {a} cannot form a prc-coalition with any singleton subset of A or B. Further, since w has more than one neighbors in {a} ∪ {u, v}, it follows that the sets {a} and {u, v} are not prc-partners. Note also that {a} does not form a prc-partition with any member of {{w}, {t, z}}, for otherwise, it is easily seen that a cycle or cycles would be created. Thus, {a} has no prc-partner, a contradiction. Hence, we may assume that [{w}, {u, v}] is not full. It is easy to verify that {a} cannot form a prc-coalition with any member of {{w}, {u, v}}, or any singleton subset of A ∪ (B \ {t, z}). Hence, {a} must form a prc-coalition with {t, z}. Note that if {t, z} ∩ A ̸= ∅, then {a} cannot form a prc-coalition with {t, z}, so {t, z} ∩ A = ∅. By symmetry, each vertex in {c, d} must form a prc-coalition with {t, z} as well. Thus, each vertex in {a, c, d} has a neighbor in {t, z}, so there exists a vertex in {t, z} having more that one neighbors in {a, c, d}, which creates cycle, a contradiction.

Claim 7. If \[|A| = 2\], then \(B = \{t, z\}\).

Proof. First we show that {t, z} ∩ A = ∅. Suppose, to the contrary, that {t, z} ∩ A ̸= ∅. Let by symmetry that t ∈ A, where A = {t, a}. Now it is not hard verifying that the set {a} has no prcpartner, a contradiction. Now we show that B = {t, z}. Suppose, to the contrary, that B ̸= {t, z}. Let b ∈ B\{t, z} and A = {a, c}. Assume first that [{w}, {u, v}] is full. It is easy to check that the set {b} cannot form a prc-coalition with any member of {{u, v}, {t, z}}, or any singleton subset of A ∪ (B \ {t, z}). Further, {b} does not form a prc-coalition with {w}, for otherwise, [{b}, {t, z}] would be full, and so we would have cycle. Thus, {b} has no prc-partner, a contradiction. Hence, we may assume that [{w}, {u, v}] is not full. It is easy to verify that no singleton subset of A has a prc-partner in {{w}, {c}, {u, v}}, implying that each of them must form a prc-coalition with {t, z}. Thus, both a and b have a neighbor in {t, z}, which contradicts the fact that T is a tree.

Now assume that |A| = 2, and so B = {t, z}. Let A = {a, b}. Observe that the set {a} (or {b}) cannot form a prc-coalition with any member of {{w}, {u, v}}, so it must form a prccoalition with {t, z}. So, in order to avoid cycles, we must have T[{a, b, t, z}] = K² ∪ K2, T[{u, v, t, z}] = K² ∪ K² and E(T[{u, v, w}]) = ∅. Hence, T ≃ P7.

Claim 8. If |A| = 1, then |B| ≤ 3.

Proof. Suppose, to the contrary, that |B| ≥ 4. Let {c, d} ⊆ B \ {t, z}. We proceed with the following claims.

Claim 8.1. [{w}, {u, v}] is not empty.

Proof. Suppose, to the contrary, that [{w}, {u, v}] = ∅. If {t, z} ∩ A = ∅, then it is easy to check that the set {c} has no prc-partner, a contradiction. Hence, we may assume {t, z} ∩ A ̸= ∅. Let by symmetry that A = {t}. One can verify that the set {c} cannot form a prc-coalition with any member of {{u, v}, {w}} or any singleton subset of B, implying that {c} must form a prccoalition with {t, z}. Let B = {c, d, e, z} and let by symmetry that zv ∈ E(T). Now the cycle T[{t, e, u, d}] would be created, a contradiction.

Claim 8.2. [{w}, {u, v}] is not full.

Proof. Suppose that the converse is true. If {t, z} ∩ A = ∅, then it is not hard verifying that the set {c} has no prc-partner, a contradiction. Hence, we may assume, by symmetry, that A = {t}. Observe that the set {c} cannot form a prc-coalition with {u, v} or any singleton subset of B. Note also that {c} has no prc-partner in {{w}, {t, z}}, for otherwise, a cycle or cycles would be created. Hence, {c} has no prc-partner, a contradiction.

Hence, we may assume |[{w}, {u, v}]| = 1. Let by symmetry that vw ∈ E(T). Assume first that {t, z} ∩ A = ∅. Let A = {a}. It is easily seen that the set {a} cannot for a prc-partition with any member of {{w}, {u, v}} or any singleton subset of B. Thus, it must form a prc-coalition with {t, z}, implying that T[{u, v, t, z}] = K² ∪ K2. Observe that the set {c} cannot form a prccoalition with any member of {A, {t, z}} or any singleton subset of B. Note also that the sets {c} and {w} are not prc-partners, for otherwise, [{c}, {t, z, u}] would be full, and so we would have a cycle, a contradiction. Thus, {c} must form a prc-coalition with {u, v}. By symmetry, {d} must form a prc-coalition with {u, v} as well. Therefore, [{a}, {c, d}] is full, creating a cycle or cycles, a contradiction. Hence we may assume, by symmetry, that A = {t}. Note that the set {t, z} cannot form a prc-coalition with any singleton subset of B, for otherwise, a cycle or cycles would be created. Further, observe that {t, z} does not form a prc-coalition with {w}. Hence, {t, z} has no prc-partner, a contradiction. This completes the proof of Claim 8. To complete the proof of theorem, we consider the following claims.

Claim 9. If |A| = 1 and |B| = 2, then T ∈ {P6, R}.

Proof. First assume A ∩ {t, z} = ∅. Let A = {a}. It is easy to verify that {a} cannot form a prc-coalition with any member of {{w}, {u, v}}, so it must form a prc-coalition with {t, z}, implying that each vertex in {t, z} has a distinct neighbor in {u, v}. If [{w}, {u, v}] is full, then T ≃ R. Otherwise, suppose first that [{w}, {u, v}] is empty. Since T is connected, a has a neighbor in {t, z}. If [{a}, {t, z}] is full, then T ≃ R. Otherwise, either uv ∈ E(T) or tz ∈ E(T), implying that either T ≃ R or T ≃ P6. Now suppose, by symmetry, that [{w}, {u, v}] = {vw} and zv ∈ E(T). If a has no neighbor in {t, z}, then either uv ∈ E(T) or tz ∈ E(T), implying that either T ≃ R or T ≃ P6. Otherwise, we have at ∈ E(T), and so T ≃ P6. Next assume A ∩ {t, z} ̸= ∅. Let by symmetry that A = {t} and B = {b, z}. Suppose first that [{w}, {u, v}] = ∅. Then the set {b} must form a prc-coalition with {t, z}, implying that each vertex in {b, z} has a

distinct neighbor in {u, v}. Since T is connected, t has a neighbor in {b, z}. Let by symmetry that tz ∈ E(T). Now for T to be connected, we must have either bz ∈ E(T) or uv ∈ E(T), implying respectively that either T = R or T = P6. Next observe that if [{w}, {u, v}] is full, then T = R. Finally, suppose that |[{w}, {u, v}]| = 1. Let by symmetry that wv ∈ E(T). If the set {t, z} forms a prc-coalition with {w}, then zu ∈ E(T). In this case, either tz ∈ E(T) or bz ∈ E(T), implying that T = P6. Otherwise, {t, z} must form a prc-coalition with {b}. In this case, it is easy to verify that either T = R or T = P6.

Claim 10. If |A| = 1 and |B| = 3, then T = P7.

Proof. First assume A ∩ {t, z} = ∅. Let A = {a} and B = {t, z, b}. If [{w}, {u, v}] = ∅, then it is easy to check that the set {b} has no prc-partner, a contradiction. Else if [{w}, {u, v}] is full, then considering the fact that T has no cycles, we observe that the set {a} has no prc-partner, a contradiction. Hence, we may assume, by symmetry, that [{w}, {u, v}] = {vw}. Note that the set {a} can only form a prc-coalition with {t, z}, implying that each vertex in {t, z} has a distinct neighbor in {u, v} and that b is dominated by {a} ∪ {t, z}. If ab /∈ E(T), then it is not hard verifying that the set {b} would have no prc-partner, so ab ∈ E(T), implying that ub ∈ E(T), and so T ≃ P7. Now assume A ∩ {t, z} ̸= ∅. Let by symmetry that A = {t}, B = {z, b, c} and vz ∈ E(T). We show that [{w}, {u, v}] ̸= ∅. Suppose the opposite is right. Observe that each of the sets {b} and {c} cannot form a prc-coalition with any member of {{w}, {u, v}}, implying that they must form a prc-coalition with {t, z}, which is again impossible since a cycle would be created. Note that [{w}, {u, v}] is not full, for otherwise, it is easy to check that the set {t, z} would have no prc-partner. Hence, we may assume, by symmetry [{w}, {u, v}] = {vw}. Note that no member of {{t, z}, {b}, {c}} can form a prc-coalition with {w}, for otherwise, we would have more that six edges, contradicting the fact that T is a tree. Thus, each of the sets {b} and {c} must form a prc-coalition with {t, z}, which is again impossible since we would have more than six edges. This completes the proof.

5. Discussion and conclusions

In this paper, we introduced the notion of perfect coalitions in graph, which extends the notion of coalitions in graphs. We obtained an upper bound on the number of coalitions involving any member in a prc-partition of a graph. This helped us determine the perfect coalition number of paths and cycles. We also obtained some results regarding graphs with large perfect coalition number. We end the paper with the following open problems.

Problem 1. Characterize graphs admitting a prc-partition.

Problem 2. Characterize graphs G in which the equality P RC(G) = C(G) holds.

Problem 3. Characterize graphs G with δ(G) = 2 and P RC(G) = |V (G)|.

Conflicts of interest

The authors declare that they have no conflict of interest.

Acknowledgments

A part of this research was conducted by the first author while he was a visiting professor in the Department of Combinatorics and Optimization at the University of Waterloo in Summer 2024.

References

• [1] S. Alikhani, D. Bakhshesh, H.R. Golmohammadi, and E.V. Konstantinova, Connected coalition in graphs, Discuss. Math. Graph Theory, inpress. https://doi.org/10.7151/dmgt.2509
• [2] D. Bakhshesh, M.A. Henning, and D. Pradhan, On the coalition number of trees, Bull. Malays. Math. Sci. Soc. 46 (2023), 95.
• [3] 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.
• [4] T.W. Haynes, J.T. Hedetniemi, S.T. Hedetniemi, A.A. McRae, and R. Mohan, Introduction to coalitions in graphs, AKCE Int. J. Graphs Comb. 17 (2020), 653–659, https://doi.org/10.1080/09728600.2020.1832874.
• [5] T.W. Haynes, J.T. Hedetniemi, S.T. Hedetniemi, A.A. McRae, and R. Mohan, Self-coalition graphs, Opuscula Math. 43 (2) (2023), 173–183, https://doi.org/10.7494/OpMath.2023.43.2.173.
• [6] 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 (3) (2021), 442–453.
• [7] T.W. Haynes, S.T. Hedetniemi, and M.A. Henning, Domination in Graphs: Core Concepts Series: Springer Monographs in Mathematics, Springer, Cham, 2023. xx + 644 pp.
• [8] T.W. Haynes, S.T. Hedetniemi, and P.J. Slater, Fundamentals of Domination in Graphs, Marcel Dekker, New York, (1998).
• [9] M A. Henning and D.A. Mojdeh, Double coalitions in graphs, Bull. Malays. Math. Sci. Soc. 48 (2025) no. 51.
• [10] M.A. Henning and D.A. Mojdeh, Double coalitions in regular graphs. Graph and Combin. 41 (2025), no. 74.
• [11] M.R. Samadzadeh and D.A. Mojdeh, Independent coalition in graphs: existence and characterization, Ars Math. Contemp. 24 (2024) # P3.09, doi:10.26493/1855-3974.3113.6f7.
• [12] M.R. Samadzadeh, D.A. Mojdeh, and R. Nadimi, Paired coalition in graphs, AKCE International Journal of Graphs and Combinatorics 22 (1) (2025), 43–54.