On the Coalition Number of Trees

Let G be a graph with vertex set V and of order n= | V| , and let δ(G) and Δ(G) be the minimum and maximum degree of G, respectively. Two disjoint sets V₁, V₂⊆ V form a coalition in G if none of them is a dominating set of G but their union V₁∪ V₂ is. A vertex partition Ψ= { V₁, … , V_k} of V is a coalition partition of G if every set V_i∈ Ψ is either a dominating set of G with the cardinality | V_i| = 1 , or is not a dominating set, but for some V_j∈ Ψ, V_i and V_j form a coalition. The maximum cardinality of a coalition partition of G is the coalition number C(G) of G. Given a coalition partition Ψ= { V₁, … , V_k} of G, a coalition graph CG (G, Ψ) is associated on Ψ such that there is a one-to-one correspondence between its vertices and the members of Ψ, where two vertices of CG (G, Ψ) are adjacent if and only if the corresponding sets form a coalition in G. In this paper, we address previously some open problems in the study of the coalitions in graphs. We characterize all graphs G with δ(G) ≤ 1 and C(G) = n, and we characterize all trees T with C(T) = n- 1. We determine the number of coalition graphs that can be defined by all coalition partitions of a given path. Furthermore, we show that there is no universal coalition path, a path whose coalition partitions define all possible coalition graphs.