On cubic graphs having the maximum coalition number Full article
| Journal |
Сибирские электронные математические известия (Siberian Electronic Mathematical Reports)
, E-ISSN: 1813-3304 |
||||
|---|---|---|---|---|---|
| Output data | Year: 2024, Volume: 21, Number: 1, Pages: 363-369 Pages count : 7 DOI: 10.33048/semi.2024.21.027 | ||||
| Tags | dominating set, coalition number, cubic graph. | ||||
| Authors |
|
||||
| Affiliations |
|
Funding (2)
| 1 | Sobolev Institute of Mathematics | FWNF-2022-0017 |
| 2 |
Министерство науки и высшего образования РФ Mathematical Center in Akademgorodok |
075-15-2019-1613, 075-15-2022-281 |
Abstract:
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 infinite family of cubic graphs satisfying C(G) = 9 is constructed.
Cite:
Dobrynin A.A.
, Golmohammadi H.
On cubic graphs having the maximum coalition number
Сибирские электронные математические известия (Siberian Electronic Mathematical Reports). 2024. V.21. N1. P.363-369. DOI: 10.33048/semi.2024.21.027 WOS Scopus
On cubic graphs having the maximum coalition number
Сибирские электронные математические известия (Siberian Electronic Mathematical Reports). 2024. V.21. N1. P.363-369. DOI: 10.33048/semi.2024.21.027 WOS Scopus
Dates:
| Submitted: | Apr 9, 2024 |
| Published print: | May 28, 2024 |
| Published online: | May 28, 2024 |
Identifiers:
| Web of science: | WOS:001283159700005 |
| Scopus: | 2-s2.0-85204484688 |
Citing:
| DB | Citing |
|---|---|
| Scopus | 1 |