Coalition graphs.

A coalition in a graph G=(V,E) consists of two disjoint sets V1 and V2 of vertices, such that neither V1 nor V2 is a dominating set, but the union V1∪V2 is a dominating set of G. A 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 dominating set consisting of a single vertex of degree n-1, or is not a dominating set but forms a coalition with another set Vj. Associated with every coalition partition π of a graph G is a graph called the coalition graph of G with respect to π, denoted CG(G,π), the vertices of which correspond one-to-one with the sets V1,V2,...,Vk of π and two vertices are adjacent in CG(G,π) if and only if their corresponding sets in π form a coalition. In this paper, we initiate the study of coalition graphs and we show that every graph is a coalition graph. [ABSTRACT FROM AUTHOR]