2023/04/15 by Bakhshesh, Davood, Henning, Michael A., Pradhan, Dinabandhu
#Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics
paper · doi:10.48550/arxiv.2304.07606
Let G be graph with vertex set V and order n=|V|. A coalition in G is a combination of two distinct sets, A⊆ V and B⊆ V, which are disjoint and are not dominating sets of G, but A∪ B is a dominating set of G. A coalition partition of G is a partition P=\S1,…,Sk\ of its vertex set V, where each set Si∈ P is either a dominating set of G with only one vertex, or it is not a dominating set but forms a coalition with some other set Sj ∈ P. The coalition number C(G) is the maximum cardinality of a coalition partition of G. To represent a coalition partition P of G, a coalition graph \CG(G, P) is created, where each vertex of the graph corresponds to a member of P and two vertices are adjacent if and only if their corresponding sets form a coalition in G. A coalition partition P of G is a singleton coalition partition if every set in P consists of a single vertex. If a graph G has a singleton coalition partition, then G is referred to as a singleton-partition graph. A graph H is called a singleton coalition graph of a graph G if there exists a singleton coalition partition P of G such that the coalition graph \CG(G,P) is isomorphic to H. A singleton coalition graph chain with an initial graph G1 is defined as the sequence G1→ G2→ G3→⋯ where all graphs Gi are singleton-partition graphs, and \CG(Gi,Γ1)=Gi+1, where Γ1 represents a singleton coalition partition of Gi. In this paper, we address two open problems posed by Haynes et al. We characterize all graphs G of order n and minimum degree δ(G)=2 such that C(G)=n and investigate the singleton coalition graph chain starting with graphs G where δ(G)≤ 2.