|
Дискретная математика и математическая кибернетика
On cubic graphs having the maximum coalition number
A. A. Dobrynina, H. Golmohammadiab a Sobolev Institute of Mathematics, pr. Koptyuga, 4, 630090, Novosibirsk, Russia
b Novosibirsk State University,
Pirogova str., 2,
630090, Novosibirsk, Russia
Аннотация:
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 graph vertices is called a coalition partition P if every non-dominating set of P is a member of a coalition, and every dominating set is a single-vertex set. The coalition number C(G) of a graph G is the maximum cardinality of its coalition partitions. It is known that for cubic graphs C(G)⩽9. The existence of cubic graphs with the maximum coalition number is an unsolved problem. In this paper, an infinite family of cubic graphs satisfying C(G)=9 is constructed.
Ключевые слова:
dominating set, coalition number, cubic graph.
Поступила 9 апреля 2024 г., опубликована 28 мая 2024 г.
Образец цитирования:
A. A. Dobrynin, H. Golmohammadi, “On cubic graphs having the maximum coalition number”, Сиб. электрон. матем. изв., 21:1 (2024), 363–369
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/semr1690 https://www.mathnet.ru/rus/semr/v21/i1/p363
|
Статистика просмотров: |
Страница аннотации: | 24 | PDF полного текста: | 7 |
|