Research output: Contribution to journal › Article › peer-review
Connected coalitions in graphs. / Alikhani, Saeid; Bakhshesh, Davood; Golmohammadi, Hamidreza et al.
In: Discussiones Mathematicae - Graph Theory, Vol. 44, No. 4, 2024, p. 1551-1566.Research output: Contribution to journal › Article › peer-review
}
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 -
ID: 59871681