Upper Bounds on the Coalition Number

Document Type


Publication Date



A dominating set in a graph G = (V,E) is a set S ⊆ V such that every vertex not in S is adjacent to at least one vertex in S. A coalition in a graph G consists of two disjoint sets V1, V2 ⊂ V neither of which is a dominating set but whose union V1∪ V2 is a dominating set. A vertex partition π = {V1, V2, …, Vk} such that every set Vi is either a dominating set consisting of a single vertex, or is not a dominating set but forms a coalition with another set Vj which is not a dominating set, is called a coalition partition. The maximum order of a coalition partition is called the coalition number of G. In this paper we obtain a tight upper bound on the coalition number of any graph G in terms of the maximum degree of G. We also give a tight upper bound on the coalition number in terms of both maximum degree and minimum degree of G.