Результаты исследований: Научные публикации в периодических изданиях › статья › Рецензирование
The shortest cycle having the maximal number of coalition graphs. / Добрынин, Андрей Алексеевич; Голмохаммади, Хамидреза .
в: Discrete Mathematics Letters, Том 14, 2024, стр. 21-26.Результаты исследований: Научные публикации в периодических изданиях › статья › Рецензирование
}
TY - JOUR
T1 - The shortest cycle having the maximal number of coalition graphs
AU - Добрынин, Андрей Алексеевич
AU - Голмохаммади, Хамидреза
PY - 2024
Y1 - 2024
N2 - 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.
AB - 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.
UR - https://www.elibrary.ru/item.asp?id=68881787
UR - https://www.mendeley.com/catalogue/bad7456e-1ee9-38df-b97c-5f3a7d32372c/
U2 - 10.47443/dml.2024.111
DO - 10.47443/dml.2024.111
M3 - Article
VL - 14
SP - 21
EP - 26
JO - Discrete Mathematics Letters
JF - Discrete Mathematics Letters
ER -
ID: 60559811