No Detail Found!

The shortest cycle having the maximal number of coalition graphs

Author(s)
Andrey A. Dobrynin Sobolev Institute of Mathematics, Siberian Branch of the Russian Academy of Sciences,Novosibirsk,Russia
Hamidreza Golmohammadi Novosibirsk State University,Pirogova Str. 2, Novosibirsk,RussiaSobolev Institute of Mathematics, Siberian Branch of the Russian Academy of Sciences,Novosibirsk,Russia
Abstract
A coalition in a graph G with a vertex set V consists of two disjoint sets V1; V2 V , such that neither V1 nor V2 is a dominating set, but the union V1 [ V2 is a dominating set in G. A partition of V is called a coalition partition if every non-dominating set of is a member of a coalition and every dominating set is a single-vertex set. Every coalition partition generates its coalition graph. The vertices of the coalition graph correspond one-to-one with the partition sets and two vertices are adjacent if and only if their corresponding sets form a coalition. In the paper [T. W. Haynes, J. T. Hedetniemi, S. T. Hedetniemi, A. A. McRae, R. Mohan, Discuss. Math. Graph Theory 43 (2023) 931-946], the authors proved that partition coalitions of cycles can generate only 27 coalition graphs and asked about the shortest cycle having the maximum number of coalition graphs. In this paper, we show that C15 is the shortest graph having this property.
Publication Details
Page(s) 21-26
Published Journal: Discrete Mathematics Letters, Volume: 14, Issue: 0, Year: 2024

Request the full text from PASTIC

Keywords
Cycle, coalition partition, coalition number
References
Alikhani S.,Bakhshesh D.,Golmohammadi H. .2024 .. , 2365365 : .
Alikhani S.,Bakhshesh D.,Golmohammadi H. . .On independent coalition in graphs and independent coalition graphs. Discuss. Math. Graph Theory, : .
Alikhani S.,Bakhshesh D.,Golmohammadi H. R.,Konstantinova E. V. . .. Discuss. Math. Graph Theory, : .
Alikhani S.,Golmohammadi H. R.,Konstantinova E. V. .2024 .Coalition of cubic graphs of order at most 10, Commun. , 9(3) : 437-450.
Bakhshesh D.,Henning M. A.,Pradhan D. .2023 .On the coalition number of trees. Bull. Malays. Math. Sci. Soc, 46 : 95.
Dobrynin A. A.,Golmohammadi H. .2024 .On cubic graphs having the maximum coalition number. , 21(1) : 356-362.
Golmohammadi H. .1813 .Total coalitions of cubic graphs of at most order 10, Commun. , 29015 : .
Haynes T. W.,Hedetniemi J. T.,Hedetniemi S. T.,McRae A. A.,Mohan R. .2020 .. AKCE Int. J. Graphs Comb, 17(2) : 653-659.
Haynes T .W.,Hedetniemi J. T.,Hedetniemi S. T.,McRae A. A.,Mohan R. .2021 .Upper bounds on the coalition number. Australas. J. Combin, 80(3) : 442-453.
Haynes T. W.,Hedetniemi J. T.,Hedetniemi S. T.,McRae A. A.,Mohan R. .2023 .Coalition graphs of paths, cycles, and trees. Discuss. Math. Graph Theory, 43 : 931-946.
Haynes T. W.,Hedetniemi J. T.,Hedetniemi S. T.,McRae A. A.,Mohan R. .2023 .. Commun. Combin. Optim, 8(2) : 423-430.
Haynes T. W.,Hedetniemi J. T.,Hedetniemi S. T.,McRae A. A.,Mohan R. .2023 .Self-coalition graphs. , 43 : 173-183.
Haynes T. W.,Hedetniemi S. T.,Henning M. A. .2020 .. , : .
Haynes T. W.,Hedetniemi S. T.,Henning M. A. .2023 .. Domination in Graphs: Core Concepts, : .
Haynes T. W.,Hedetniemi S. T.,Slater P. J. .1998 .. , : .
Sloane N. J. A. . .. The On-Line Encyclopedia of Integer Sequences, : .
0

Citations

0

Downloads

34

Views