Self-coalition graphs

• Autorzy: Haynes Teresa W. , Hedetniemi Jason T. , Hedetniemi Stephen T. , McRae Alice A. , Mohan Raghuveer

Identyfikatory

DOI

10.7494/OpMath.2023.43.2.173

• Języki publikacji: EN

Abstrakty

EN

A coalition in a graph G = (V,E) consists of two disjoint sets V1 and V2 of vertices, such that neither V1 nor V2 is a dominating set, but the union V1 ∪ V2 is a dominating set of G. A coalition partition in a graph G of order n = |V | is a vertex partition π = {V1, V2, . . . , Vk} 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. The singleton partition π1 of the vertex set of G is a partition of order |V |, that is, each vertex of G is in a singleton set of the partition. A graph G is called a self-coalition graph if G is isomorphic to its coalition graph CG(G, π1), where π1 is the singleton partition of G. In this paper, we characterize self-coalition graphs.

Słowa kluczowe

EN

coalitions in graphs; coalition partitions; coalition graphs; domination

• Wydawca: AGH University of Science and Technology Press
• Czasopismo: Opuscula Mathematica
• Rocznik: 2023
• Tom: Vol. 43, no. 2
• Strony: 173--183
• Opis fizyczny: Bibliogr. 4 poz.

Twórcy

autor

Haynes Teresa W.

• East Tennessee State University, Department of Mathematics and Statistics, Johnson City, TN 37614, USA
• University of Johannesburg, Department of Mathematics, Auckland Park, South Africa

autor

Hedetniemi Jason T.

• Department of Mathematics, Wilkes Honors College, Florida Atlantic University, Jupiter, FL 33458, USA

autor

Hedetniemi Stephen T.

• Professor Emeritus, Clemson University, School of Computing, Clemson, SC 29634, USA

autor

McRae Alice A.

• Appalachian State University, Computer Science Department, Boone, NC 28608, USA

autor

Mohan Raghuveer

• Appalachian State University, Computer Science Department, Boone, NC 28608, USA

Bibliografia

• [1] T.W. Haynes, J.T. Hedetniemi, S.T. Hedetniemi, A.A. McRae, R. Mohan, Introduction to coalitions in graphs, AKCE Int. J. Graphs Combin. 17 (2020), no. 2, 653–659.
• [2] T.W. Haynes, J.T. Hedetniemi, S.T. Hedetniemi, A.A. McRae, R. Mohan, Upper bounds on the coalition number, Austral. J. Combin. 80 (2021), no. 3, 442–453.
• [3] T.W. Haynes, J.T. Hedetniemi, S.T. Hedetniemi, A.A. McRae, R. Mohan, Coalition graphs of paths, cycles, and trees, Discuss. Math. Graph Theory, in press.
• [4] T.W. Haynes, J.T. Hedetniemi, S.T. Hedetniemi, A.A. McRae, R. Mohan, Coalition graphs, Comm. Combin. Optim. 8 (2023), no. 2, 423–430.

Uwagi

Opracowanie rekordu ze środków MEiN, umowa nr SONP/SP/546092/2022 w ramach programu "Społeczna odpowiedzialność nauki" - moduł: Popularyzacja nauki i promocja sportu (2022-2023)