Connected coalitions in graphs | Sciact

Connected coalitions in graphs Full article

Journal

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

Output data

Year: 2024, Volume: 44, Number: 4, Pages: 1551-1566 Pages count : 16 DOI: 10.7151/dmgt.2509

Tags

connected coalition partition; polynomial-time algorithm

Authors

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

Affiliations

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

Funding (1)

Russian Science Foundation

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

Submitted:	Feb 26, 2023
Accepted:	Jul 9, 2023
Published online:	Jul 27, 2023
Published print:	Apr 2, 2024

Web of science:	WOS:001146192500001
Scopus:	2-s2.0-85202669259
Elibrary:	62745556
OpenAlex:	W4386289568

DB	Citing
OpenAlex	7
Web of science	6
Scopus	9