RUS  ENG
Full version
JOURNALS // Sibirskie Èlektronnye Matematicheskie Izvestiya [Siberian Electronic Mathematical Reports] // Archive

Sib. Èlektron. Mat. Izv., 2024 Volume 21, Issue 1, Pages 363–369 (Mi semr1690)

Discrete mathematics and mathematical cybernetics

On cubic graphs having the maximum coalition number

A. A. Dobrynina, H. Golmohammadiab

a Sobolev Institute of Mathematics, pr. Koptyuga, 4, 630090, Novosibirsk, Russia
b Novosibirsk State University, Pirogova str., 2, 630090, Novosibirsk, Russia

Abstract: 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.

UDC: 519.17

MSC: 05C69

Received April 9, 2024, published May 28, 2024

Language: English

DOI: doi.org/10.33048/semi.2024.21.027



© Steklov Math. Inst. of RAS, 2024