Research output: Contribution to journal › Article › peer-review
On cubic graphs having the maximum coalition number. / Dobrynin, A. A.; Golmohammadi, H.
In: Siberian Electronic Mathematical Reports, Vol. 21, No. 1, 2024, p. 363-369.Research output: Contribution to journal › Article › peer-review
}
TY - JOUR
T1 - On cubic graphs having the maximum coalition number
AU - Dobrynin, A. A.
AU - Golmohammadi, H.
N1 - The study of A.A. Dobrynin was supported by the state contract of the Sobolev Institute of Mathematics (project number FWNF-2022-0017) and the work of Hamidreza Golmohammadi was supported by the Mathematical Center in Akademgorodok, under agreement No. 075-15-2022-281 with the Ministry of Science and High Education of the Russian Federation.
PY - 2024
Y1 - 2024
N2 - 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 in nite family of cubic graphs satisfying C(G) = 9 is constructed.
AB - 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 in nite family of cubic graphs satisfying C(G) = 9 is constructed.
KW - coalition number
KW - cubic graph
KW - dominating set
UR - https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85204484688&origin=inward
UR - https://www.mendeley.com/catalogue/44f69f0d-1fe6-3e94-bb26-b3f066cd53d4/
U2 - 10.33048/semi.2024.21.027
DO - 10.33048/semi.2024.21.027
M3 - Article
VL - 21
SP - 363
EP - 369
JO - Сибирские электронные математические известия
JF - Сибирские электронные математические известия
SN - 1813-3304
IS - 1
ER -
ID: 60559724