The shortest cycle having the maximal number of coalition graphs | [Discrete Mathematics Letters • 2024]

Author(s):

1. Andrey A. Dobrynin: Sobolev Institute of Mathematics, Siberian Branch of the Russian Academy of Sciences,Novosibirsk,Russia

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

Page(s): 21-26

DOI: 10.47443/dml.2024.111

Published: Journal: Discrete Mathematics Letters, Volume: 14, Issue: 0, Year: 2024

Keywords:

Cycle , coalition partition , coalition number

References:

[1] Alikhani S.,Bakhshesh D.,Golmohammadi H. .2024 .. , 2365365 : .

[2] Alikhani S.,Bakhshesh D.,Golmohammadi H. . .On independent coalition in graphs and independent coalition graphs. Discuss. Math. Graph Theory, : .

[3] Alikhani S.,Bakhshesh D.,Golmohammadi H. R.,Konstantinova E. V. . .. Discuss. Math. Graph Theory, : .

[4] Alikhani S.,Golmohammadi H. R.,Konstantinova E. V. .2024 .Coalition of cubic graphs of order at most 10, Commun. , 9(3) : 437-450.

[5] Bakhshesh D.,Henning M. A.,Pradhan D. .2023 .On the coalition number of trees. Bull. Malays. Math. Sci. Soc, 46 : 95.

[6] Dobrynin A. A.,Golmohammadi H. .2024 .On cubic graphs having the maximum coalition number. , 21(1) : 356-362.

[7] Golmohammadi H. .1813 .Total coalitions of cubic graphs of at most order 10, Commun. , 29015 : .

[8] Haynes T. W.,Hedetniemi J. T.,Hedetniemi S. T.,McRae A. A.,Mohan R. .2020 .. AKCE Int. J. Graphs Comb, 17(2) : 653-659.

[9] 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.

[10] 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.

[11] Haynes T. W.,Hedetniemi J. T.,Hedetniemi S. T.,McRae A. A.,Mohan R. .2023 .. Commun. Combin. Optim, 8(2) : 423-430.

[12] Haynes T. W.,Hedetniemi J. T.,Hedetniemi S. T.,McRae A. A.,Mohan R. .2023 .Self-coalition graphs. , 43 : 173-183.

[13] Haynes T. W.,Hedetniemi S. T.,Henning M. A. .2020 .. , : .

[14] Haynes T. W.,Hedetniemi S. T.,Henning M. A. .2023 .. Domination in Graphs: Core Concepts, : .

[15] Haynes T. W.,Hedetniemi S. T.,Slater P. J. .1998 .. , : .

[16] Sloane N. J. A. . .. The On-Line Encyclopedia of Integer Sequences, : .

Citations

Citations are not available for this document.

Citations

Downloads

Views