TY - JOUR
ID - 14431
TI - Coalition Graphs
JO - Communications in Combinatorics and Optimization
JA - CCO
LA - en
SN - 2538-2128
AU - Haynes, Teresa W.
AU - Hedetniemi, Jason T.
AU - Hedetniemi, Stephen T
AU - McRae, Alice
AU - Mohan, Raghuveer
AD - East Tennessee State University;
Department of Mathematics
University of Johannesburg
AD - Florida Atlantic University
AD - Professor Emeritus
Clemson University
Clemson, South Carolina
AD - Appalachian State University
Y1 - 2023
PY - 2023
VL - 8
IS - 2
SP - 423
EP - 430
KW - dominating set
KW - Coalition
KW - independent dominating set
DO - 10.22049/cco.2022.27916.1394
N2 - A coalition in a graph $G = (V, E)$ consists of two disjoint sets $V_1$ and $V_2$ of vertices, such that neither $V_1$ nor $V_2$ is a dominating set, but the 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}$ 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$. 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 initiate the study of coalition graphs and we show that every graph is a coalition graph.
UR - http://comb-opt.azaruniv.ac.ir/article_14431.html
L1 - http://comb-opt.azaruniv.ac.ir/article_14431_a7f093b82d7cfb1bf521fdf78f7dd886.pdf
ER -