Geodesic
Coalition graphs of paths, cycles, and trees
Discussiones Mathematicae. Graph Theory, Tome 43 (2023) no. 4, pp. 931-946

Voir la notice de l'article provenant de la source Library of Science

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 ∪ V_2 is a dominating set of G. A coalition partition in a graph G of order n = |V| is a vertex partition π = {V_1, V_2, … , 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 π of a graph G is a graph called the coalition graph of G with respect to π, denoted CG(G,π), the vertices of which correspond one-to-one with the sets V_1, V_2, …, V_k of π and two vertices are adjacent in CG(G,π) if and only if their corresponding sets in π 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 
@article{DMGT_2023_43_4_a3,
     author = {Haynes, Teresa W. and Hedetniemi, Jason T. and Hedetniemi, Stephen T. and McRae, Alice A. and Mohan, Raghuveer},
     title = {Coalition graphs of paths, cycles, and trees},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {931--946},
     publisher = {mathdoc},
     volume = {43},
     number = {4},
     year = {2023},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2023_43_4_a3/}
}
TY  - JOUR
AU  - Haynes, Teresa W.
AU  - Hedetniemi, Jason T.
AU  - Hedetniemi, Stephen T.
AU  - McRae, Alice A.
AU  - Mohan, Raghuveer
TI  - Coalition graphs of paths, cycles, and trees
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2023
SP  - 931
EP  - 946
VL  - 43
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2023_43_4_a3/
LA  - en
ID  - DMGT_2023_43_4_a3
ER  - 
%0 Journal Article
%A Haynes, Teresa W.
%A Hedetniemi, Jason T.
%A Hedetniemi, Stephen T.
%A McRae, Alice A.
%A Mohan, Raghuveer
%T Coalition graphs of paths, cycles, and trees
%J Discussiones Mathematicae. Graph Theory
%D 2023
%P 931-946
%V 43
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2023_43_4_a3/
%G en
%F DMGT_2023_43_4_a3
Haynes, Teresa W.; Hedetniemi, Jason T.; Hedetniemi, Stephen T.; McRae, Alice A.; Mohan, Raghuveer. Coalition graphs of paths, cycles, and trees. Discussiones Mathematicae. Graph Theory, Tome 43 (2023) no. 4, pp. 931-946. http://geodesic.mathdoc.fr/item/DMGT_2023_43_4_a3/