Geodesic
On cubic graphs having the maximum coalition number
Sibirskie èlektronnye matematičeskie izvestiâ, Tome 21 (2024) no. 1, pp. 363-369

Voir la notice de l'article provenant de la source Math-Net.Ru

A coalition in a graph $G$ with a vertex set $V$ consists of two disjoint sets $V_1, V_2\subset V$, such that neither $V_1$ nor $V_2$ is a dominating set, but the union $V_1\cup V_2$ is a dominating set in $G$. A partition of graph vertices is called a coalition partition $\mathcal{P}$ if every non-dominating set of $\mathcal{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) \le 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.
Keywords: dominating set, coalition number, cubic graph. 
@article{SEMR_2024_21_1_a19,
     author = {A. A. Dobrynin and H. Golmohammadi},
     title = {On cubic graphs having the maximum coalition number},
     journal = {Sibirskie \`elektronnye matemati\v{c}eskie izvesti\^a},
     pages = {363--369},
     publisher = {mathdoc},
     volume = {21},
     number = {1},
     year = {2024},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/SEMR_2024_21_1_a19/}
}
TY  - JOUR
AU  - A. A. Dobrynin
AU  - H. Golmohammadi
TI  - On cubic graphs having the maximum coalition number
JO  - Sibirskie èlektronnye matematičeskie izvestiâ
PY  - 2024
SP  - 363
EP  - 369
VL  - 21
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/SEMR_2024_21_1_a19/
LA  - en
ID  - SEMR_2024_21_1_a19
ER  - 
%0 Journal Article
%A A. A. Dobrynin
%A H. Golmohammadi
%T On cubic graphs having the maximum coalition number
%J Sibirskie èlektronnye matematičeskie izvestiâ
%D 2024
%P 363-369
%V 21
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/SEMR_2024_21_1_a19/
%G en
%F SEMR_2024_21_1_a19
A. A. Dobrynin; H. Golmohammadi. On cubic graphs having the maximum coalition number. Sibirskie èlektronnye matematičeskie izvestiâ, Tome 21 (2024) no. 1, pp. 363-369. http://geodesic.mathdoc.fr/item/SEMR_2024_21_1_a19/