The shortest cycle having the maximal number of coalition graphs

The shortest cycle having the maximal number of coalition graphs Full article

Journal

Discrete Mathematics Letters
ISSN: 2664-2557

Output data

Year: 2024, Volume: 14, Pages: 21-26 Pages count : 6 DOI: 10.47443/dml.2024.111

Funding (2)

1	Sobolev Institute of Mathematics	FWNF-2022-0017
2	Министерство науки и высшего образования РФ Mathematical Center in Akademgorodok	075-15-2019-1613, 075-15-2022-281

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.

Dobrynin A.A. , Golmohammadi H.
The shortest cycle having the maximal number of coalition graphs
Discrete Mathematics Letters. 2024. V.14. P.21-26. DOI: 10.47443/dml.2024.111 WOS Scopus РИНЦ OpenAlex

Submitted:	May 17, 2024
Accepted:	Jul 17, 2024
Published print:	Jul 18, 2024
Published online:	Jul 18, 2024

Web of science:	WOS:001281072900003
Scopus:	2-s2.0-85215625913
Elibrary:	68881787
OpenAlex:	W4400724644

Пока нет цитирований