错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Singleton coalition graph chains

  • Davood Bakhshesh,
  • Michael A. Henning,
  • Dinabandhu Pradhan

摘要

Let G be a graph with vertex set V and order \(n=|V|\) n = | V | . A coalition in G is a combination of two distinct sets, \(A\subseteq V\) A V and \(B\subseteq V\) B V , which are disjoint and are not dominating sets of G, but their union \(A\cup B\) A B is a dominating set of G. A coalition partition of G is a partition \({\mathcal {P}}=\{S_1,\ldots , S_k\}\) P = { S 1 , , S k } of its vertex set V, where each set \(S_i\in {\mathcal {P}}\) S i 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 \(S_j \in {\mathcal {P}}\) S j P . The coalition number C(G) is the maximum cardinality of a coalition partition of G. To represent a coalition partition \({\mathcal {P}}\) P of G, a coalition graph \(\textrm{CG}(G, {\mathcal {P}})\) CG ( G , P ) is created, where each vertex of the graph corresponds to a member of \({\mathcal {P}}\) P and two vertices are adjacent if and only if their corresponding sets form a coalition in G. A coalition partition \({\mathcal {P}}\) P of G is a singleton coalition partition if every set in \({\mathcal {P}}\) 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 \({\mathcal {P}}\) P of G such that the coalition graph \(\textrm{CG}(G,{\mathcal {P}})\) CG ( G , P ) is isomorphic to H. A singleton coalition graph chain with an initial graph \(G_1\) G 1 is defined as the sequence \(G_1\rightarrow G_2\rightarrow G_3\rightarrow \cdots \) G 1 G 2 G 3 where all graphs \(G_i\) G i are singleton-partition graphs, and \(\textrm{CG}(G_i, \varGamma _1)=G_{i+1}\) CG ( G i , Γ 1 ) = G i + 1 , where \(\varGamma _1\) Γ 1 represents a singleton coalition partition of \(G_i\) G i . In this paper, we address two open problems posed by Haynes et al. We characterize all graphs G of order n and minimum degree \(\delta (G)=2\) δ ( G ) = 2 such that \( C(G )= n\) C ( G ) = n . Additionally, we investigate the singleton coalition graph chain starting with graphs G, where \(\delta (G)\le 2\) δ ( G ) 2 .