TY - JOUR

T1 - Connected coalitions in graphs

AU - Alikhani, Saeid

AU - Bakhshesh, Davood

AU - Golmohammadi, Hamidreza

AU - Konstantinova, Elena V.

N1 - The work of Hamidreza Golmohammadi and Elena V. Konstantinova is supported by the Russian Science Foundation under grant no. 23-21-00459. The authors would like to express their gratitude to the referees for their careful reading and helpful comments.

PY - 2024

Y1 - 2024

N2 - Let G = (V,E) be a graph, and define a connected coalition as a pair of disjoint vertex sets U1and U2such that U1∪U2forms a connected dominating set, but neither U1nor U2individually forms a connected dominating set. A connected coalition partition of G is a partition Φ = {U1,U2, . . . ,Uk} of the vertices such that each set Ui ∈ Φ either consists of only a single vertex with degree n - 1, or forms a connected coalition with another set Uj ∈ Φ that is not a connected dominating set. The connected coalition number CC(G) is defined as the largest possible size of a connected coalition partition for G. The objective of this study is to initiate an examination into the notion of connected coalitions in graphs and present essential findings. More precisely, we provide a thorough characterization of all graphs possessing a connected coalition partition. Moreover, we establish that, for any graph G with order n, a minimum degree of 1, and no full vertex, the condition CC(G) < n holds. In addition, we prove that any tree T achieves CC(T) = 2. Lastly, we propose two polynomial-time algorithms that determine whether a given connected graph G of order n satisfies CC(G) = n or CC(G) = n - 1.

AB - Let G = (V,E) be a graph, and define a connected coalition as a pair of disjoint vertex sets U1and U2such that U1∪U2forms a connected dominating set, but neither U1nor U2individually forms a connected dominating set. A connected coalition partition of G is a partition Φ = {U1,U2, . . . ,Uk} of the vertices such that each set Ui ∈ Φ either consists of only a single vertex with degree n - 1, or forms a connected coalition with another set Uj ∈ Φ that is not a connected dominating set. The connected coalition number CC(G) is defined as the largest possible size of a connected coalition partition for G. The objective of this study is to initiate an examination into the notion of connected coalitions in graphs and present essential findings. More precisely, we provide a thorough characterization of all graphs possessing a connected coalition partition. Moreover, we establish that, for any graph G with order n, a minimum degree of 1, and no full vertex, the condition CC(G) < n holds. In addition, we prove that any tree T achieves CC(T) = 2. Lastly, we propose two polynomial-time algorithms that determine whether a given connected graph G of order n satisfies CC(G) = n or CC(G) = n - 1.

UR - https://www.scopus.com/record/display.uri?eid=2-s2.0-85202669259&origin=inward&txGid=cc1e4961869699fc1c0ae6b69157c14a

UR - https://www.mendeley.com/catalogue/1a6ea458-9b3a-3c9b-902c-6cccf6c13e05/

U2 - 10.7151/dmgt.2509

DO - 10.7151/dmgt.2509

M3 - Article

VL - 44

SP - 1551

EP - 1566

JO - Discussiones Mathematicae - Graph Theory

JF - Discussiones Mathematicae - Graph Theory

SN - 1234-3099

IS - 4

ER -