Singleton coalition graph chains

DOI10.1007/S40314-023-02588-0MaRDI QIDQ6125425zbMATH OpenWikidataFDO

Authors Davood Bakhshesh, Michael A. Henning, D. Pradhan

Publication date 11 April 2024

Published in Computational and Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2304.07606

zbMATH Keywords

domination numbercoalition graphscoalition numbercoalition partition

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Abstract: Let $G$ be graph with vertex set $V$ and order $n=|V|$. A coalition in $G$ is a combination of two distinct sets, $AsubseteqV$ and $BsubseteqV$, which are disjoint and are not dominating sets of $G$, but $AcupB$ is a dominating set of $G$. A coalition partition of $G$ is a partition $mathcalP=S_1,ldots,S_k$ of its vertex set $V$, where each set $S_{i}inmathcalP$ 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}inmathcalP$. The coalition number $C(G)$ is the maximum cardinality of a coalition partition of $G$. To represent a coalition partition $mathcalP$ of $G$, a coalition graph $CG(G,mathcalP)$ is created, where each vertex of the graph corresponds to a member of $mathcalP$ and two vertices are adjacent if and only if their corresponding sets form a coalition in $G$. A coalition partition $mathcalP$ of $G$ is a singleton coalition partition if every set in $mathcalP$ 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 $mathcalP$ of $G$ such that the coalition graph $CG(G,mathcalP)$ is isomorphic to $H$. A singleton coalition graph chain with an initial graph $G_1$ is defined as the sequence $G_{1}ightarrow{G}_{2}ightarrow{G}_{3}ightarrowcdots$ where all graphs $G_i$ are singleton-partition graphs, and $CG(G_i,Gamm{a}_1)=G_{i+1}$, where $Gamm{a}_1$ represents a singleton coalition partition of $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$ such that $C(G)=n$ and investigate the singleton coalition graph chain starting with graphs $G$ where $delta(G)le2$.

Recommendations

• Coalition graphs
• Self-coalition graphs
• Introduction to coalitions in graphs
• On the coalition number of trees

Cites work

• Coalition graphs
• Introduction to coalitions in graphs
• On the coalition number of trees
• Structures of domination in graphs
• Topics in Domination in Graphs
• Total domination in graphs
• Upper bounds on the coalition number

Cited in

(8)

• Double coalitions in regular graphs
• Double coalitions in graphs
• A characterization of graphs with given total coalition numbers
• Total coalitions in claw-free cubic graphs containing double-bonded triangle-units
• Characterizations of graphs with equal vertex and coalition number
• Transversal coalitions in hypergraphs
• Universal cycles that generate all graphs of coalition partitions in cycles
• k-coalitions in graphs

This page was built for publication: Singleton coalition graph chains

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6125425)