On the Coalition Number of Trees

Let G be a graph with vertex set V and of order n = vertical bar V vertical bar, and let delta(G) and Delta(G) be the minimum and maximum degree of G, respectively. Two disjoint sets V-1, V-2 subset of V form a coalition in G if none of them is a dominating set of G but their union V-1 boolean OR V-2 is. A vertex partition psi = {V-1,..., V-k} of V is a coalition partition of G if every set V-i is an element of psi is either a dominating set of G with the cardinality vertical bar V-i vertical bar = 1, or is not a dominating set, but for some V-j is an element of psi 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 psi = {V-1,..., V-k} of G, a coalition graph CG(G, psi) is associated on psi such that there is a one-to-one correspondence between its vertices and the members of psi where two vertices of CG(G, psi) 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 delta(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.