Abstract: A subset D ⊆ V is a dominating set of a graph G with vertex set V if every vertex v ∈ V \D is adjacent to a vertex in D. Two subsets of V form a coalition if neither of them is a dominating set, but their union is a dominating set. A coalition partition of G is its vertex partition π such that every non-dominating set of π is a member of some coalition, and every dominating set is a single-vertex set in π. The coalition number C(G) of a graph G is the maximum cardinality of its coalition partitions. A subset R ⊆ V is a restrained dominating set if R is a dominating set and any vertex of V \R has at least one neighbor in V \R. Restrained dominating coalition, restrained dominating partition and restrained coalition number RC(G) are defined by the same way. In this paper, we prove that RC(G) ≤ C(G) for an arbitrary graph G. In addition, some previous results from [A. H. S. Nesam, S. Amutha, N. Anbazhagan, Stat. Optim. Inf. Comput. 14 (2025) 3409–3417] are corrected by determining the exact value of the restrained coalition number of cycles.

Cite: Dobrynin A.A. , Glebov A.N. , Golmohammadi H.
On restrained coalitions in graphs: bounds and exact values
Discrete Mathematics Letters. 2026. V.17. P.57-63. DOI: 10.47443/dml.2025.223 OpenAlex

Dates:

Submitted:	Dec 12, 2025
Accepted:	Apr 18, 2026
Published online:	May 13, 2026

Identifiers:

≡ OpenAlex:

W7161000446

Altmetrics: