Singleton coalition graph chains

Davood Bakhshesh, Michael A. Henning, Dinabandhu Pradhan

Research output: Contribution to journalArticlepeer-review


Let G be a 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 their union 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(Gi1)=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. Additionally, we investigate the singleton coalition graph chain starting with graphs G, where δ(G)≤2.

Original languageEnglish
Article number85
JournalComputational and Applied Mathematics
Issue number2
Publication statusPublished - Mar 2024


  • Coalition graphs
  • Coalition number
  • Coalition partition
  • Domination number

ASJC Scopus subject areas

  • Computational Mathematics
  • Applied Mathematics


Dive into the research topics of 'Singleton coalition graph chains'. Together they form a unique fingerprint.

Cite this