TY - JOUR
T1 - Singleton coalition graph chains
AU - Bakhshesh, Davood
AU - Henning, Michael A.
AU - Pradhan, Dinabandhu
N1 - Publisher Copyright:
© The Author(s) under exclusive licence to Sociedade Brasileira de Matemática Aplicada e Computacional 2024.
PY - 2024/3
Y1 - 2024/3
N2 - 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(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. Additionally, we investigate the singleton coalition graph chain starting with graphs G, where δ(G)≤2.
AB - 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(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. Additionally, we investigate the singleton coalition graph chain starting with graphs G, where δ(G)≤2.
KW - Coalition graphs
KW - Coalition number
KW - Coalition partition
KW - Domination number
UR - http://www.scopus.com/inward/record.url?scp=85188348676&partnerID=8YFLogxK
U2 - 10.1007/s40314-023-02588-0
DO - 10.1007/s40314-023-02588-0
M3 - Article
AN - SCOPUS:85188348676
SN - 2238-3603
VL - 43
JO - Computational and Applied Mathematics
JF - Computational and Applied Mathematics
IS - 2
M1 - 85
ER -