1. bookAHEAD OF PRINT
Journal Details
License
Format
Journal
eISSN
2083-5892
First Published
13 Apr 2013
Publication timeframe
4 times per year
Languages
English
access type Open Access

Coalition Graphs of Paths, Cycles, and Trees

Published Online: 08 Jul 2021
Volume & Issue: AHEAD OF PRINT
Page range: -
Received: 26 Oct 2020
Accepted: 15 May 2021
Journal Details
License
Format
Journal
eISSN
2083-5892
First Published
13 Apr 2013
Publication timeframe
4 times per year
Languages
English
Abstract

A coalition in a graph G =(V, E) consists of two disjoint sets of vertices V1 and V2, neither of which is a dominating set of G but whose union V1V2 is a dominating set of G.A coalition partition in a graph G of order n = |V | is a vertex partition π = {V1, V2,..., Vk} of V such that every set Vi 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 Vj 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 V1, V2,..., Vk 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

MSC 2010

[1] T.W. Haynes, J.T. Hedetniemi, S.T. Hedetniemi, A.A. McRae and R. Mohan, Introduction to coalitions in graphs,AKCEInt.J.Graphs Comb. 17 (2020) 653–659. https://doi.org/10.1080/09728600.2020.183287410.1080/09728600.2020.1832874Search in Google Scholar

[2] T.W. Haynes, J.T. Hedetniemi, S.T. Hedetniemi, A.A. McRae and R. Mohan, Coalition graphs, J. Combin. Math. Combin. Comput., in-press.Search in Google Scholar

Recommended articles from Trend MD

Plan your remote conference with Sciendo