DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

https://doi.org/10.7151/dmgt

Discussiones Mathematicae Graph Theory

Journal Impact Factor (JIF 2022): 0.7

5-year Journal Impact Factor (2022): 0.7

CiteScore (2022): 1.9

SNIP (2022): 0.902

Discussiones Mathematicae Graph Theory

Article in volume


Authors:

T. W. Haynes

Teresa W Haynes

Department of Mathematics and Statistics, East Tenessee State University

email: haynes@etsu.edu

0000-0002-0865-0871

J.T. Hedetniemi

Jason Hedetniemi

Florida Atlantic University

Jupiter, FL 33458
United States

email: j.hedetniemi@wingate.edu

S.T. Hedetniemi

Stephen T. Hedetniemi

Clemson Universty, Clemson, SC

email: hedet@clemson.edu

A. A. McRae

Alice A McRae

Appalachian State University

email: alice.mcrae@gmail.com

R. Mohan

Raghuveer Mohan

Appalachian State University

email: mohanr@appstate.edu

Title:

Coalition graphs of paths, cycles, and trees

PDF

Source:

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:

  1. 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
  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.

Close