Upper Bounds on the Coalition Number
Document Type
Article
Publication Date
1-1-2021
Description
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.
Citation Information
Haynes, Teresa W.; Hedetniemi, Jason T.; Hedetniemi, Stephen T.; McRae, Alice A.; and Mohan, Raghuveer, "Upper Bounds on the Coalition Number" (2021). ETSU Faculty Works. 577.
https://dc.etsu.edu/etsu-works-2/577