Connected coalitions in graphs | Sciact - Система учета научной деятельности ИМ СО РАН

Connected coalitions in graphs Научная публикация

Журнал

Discussiones Mathematicae - Graph Theory
ISSN: 1234-3099 , E-ISSN: 2083-5892

Вых. Данные

Год: 2024, Том: 44, Номер: 4, Страницы: 1551-1566 Страниц : 16 DOI: 10.7151/dmgt.2509

Ключевые слова

connected coalition partition; polynomial-time algorithm

Авторы

Alikhani Saeid ¹ , Bakhshesh Davood ² , Golmohammadi Hamidreza ^3,4 , Konstantinova Elena V. ^3,4

Организации

1	Department o fMathematical Sciences Yazd University, 89195-741, Yazd, Iran
2	Department of Computer Science, University of Bojnord, Bojnord, Iran
3	Novosibirsk State University
4	Sobolev Institute of Mathematics

Информация о финансировании (1)

Российский научный фонд

23-21-00459

In this paper we give a thorough characterisation of graphs possessing a connected coalition partition. We also study the connected coalition number CC(G) in a graph G defined as the largest size of a connected coalition partition. It is shown that CC(G)<n for any simple graph G of order n with vertices of degree one but with no vertices of degree n-1, and CC(T)=2 for a tree T. Finally, polynomial-time algorithms for determining whether a given connected graph G of order n satisfies CC(G)=n or CC(G)=n-1 are presented.

Alikhani S. , Bakhshesh D. , Golmohammadi H. , Konstantinova E.V.
Connected coalitions in graphs
Discussiones Mathematicae - Graph Theory. 2024. V.44. N4. P.1551-1566. DOI: 10.7151/dmgt.2509 WOS Scopus РИНЦ OpenAlex

Поступила в редакцию:	26 февр. 2023 г.
Принята к публикации:	9 июл. 2023 г.
Опубликована online:	27 июл. 2023 г.
Опубликована в печати:	2 апр. 2024 г.

Web of science:	WOS:001146192500001
Scopus:	2-s2.0-85202669259
РИНЦ:	62745556
OpenAlex:	W4386289568

БД	Цитирований
OpenAlex	10
Web of science	16
Scopus	17