Article in volume
Authors:
Title:
Coalition graphs of paths, cycles, and trees
PDFSource:
Discussiones Mathematicae Graph Theory 43(4) (2023) 931-946
Received: 2020-10-26 , Revised: 2021-05-10 , Accepted: 2021-05-15 , Available online: 2021-06-24 , https://doi.org/10.7151/dmgt.2416
Abstract:
A coalition in a graph $G = (V, E)$ consists of two disjoint sets of
vertices $V_1$ and $V_2$, neither of which is a dominating set of $G$ but whose
union $V_1 \cup V_2$ is a dominating set of $G$. A coalition partition
in a graph $G$ of order $n = |V|$ is a vertex partition $\pi = \{V_1, V_2,
\ldots, V_k\}$ of $V$ such that every set $V_i$ either is a dominating set
consisting of a single vertex of degree $n-1$, or is not a dominating set but
forms a coalition with another set $V_j$ which is not a dominating set.
Associated with every coalition partition $\pi$ of a graph $G$ is a graph
called the coalition graph of $G$ with respect to $\pi$, denoted
$CG(G,\pi)$, the vertices of which correspond one-to-one with the sets
$V_1, V_2, \ldots, V_k$ of $\pi$ and two vertices are adjacent in $CG(G,\pi)$
if and only if their corresponding sets in $\pi$ form a coalition. In this
paper we study coalition graphs, focusing on the coalition graphs of paths,
cycles, and trees. We show that there are only finitely many coalition graphs
of paths and finitely many coalition graphs of cycles and we identify precisely
what they are. On the other hand, we show that there are infinitely many
coalition graphs of trees and characterize this family of graphs.
Keywords:
vertex partition, dominating set, coalition
References:
- T.W. Haynes, J.T. Hedetniemi, S.T. Hedetniemi, A.A. McRae and R. Mohan, Introduction to coalitions in graphs, AKCE Int. J. Graphs Comb. 17 (2020) 653–659.
https://doi.org/10.1080/09728600.2020.1832874 - T.W. Haynes, J.T. Hedetniemi, S.T. Hedetniemi, A.A. McRae and R. Mohan, Coalition graphs, J. Combin. Math. Combin. Comput., in press.
Close