Roman coalition partitions in graphs

Roman coalition partitions in graphs Full article

Journal

Communications in Combinatorics and Optimization
ISSN: 2538-2128 , E-ISSN: 2538-2136

Output data

Year: 2026, DOI: 10.22049/cco.2026.30582.2542

Tags

coalition, Roman coalition, Roman dominating set, Roman coalition partition

Authors

Tripodoro Juan Carlos Valenzuela ¹ , Golmohammadi Hamidreza ² , Chellali Mustapha ³

Affiliations

1	Department of Mathematics, University of Cadiz, Spain
2	Sobolev Institute of Mathematics, Ak. Koptyug av. 4, Novosibirsk, 630090, Russia
3	LAMDA-RO Laboratory, Dept. of Mathematics, Univ. of Blida, Blida, Algeria

Funding (1)

Министерство науки и высшего образования РФ

FWNF-2026-0011

The Roman domination problem is a combinatorial optimization problem on a graph asking to assign a label from 012 to each vertex feasibly, such that the total sum of assigned labels is minimized. Let G = (VE) be a graph, and let U1U2 V be two non-empty disjoint subsets. We say that the pair U1U2 is Roman-feasible if there exists a Roman dominating function f : V 012 such that V0 = V (U1 U2) V1 =Ui and V2 =U3 i for some i 12 where Vj denotes the set of vertices assigned label j by f. The set U1U2U3 is a Roman coalition if the following two conditions hold: (i) the pair Ui Uj is not Roman-feasible for any di erent 1 i j 3; (ii) there exists k such that the pair Ui Uj Uk is Romanfeasible, where i jk = 123 The purpose of this paper is to introduce and study the new concept of Roman coalitions in graphs, providing basic properties, lower and upper bounds, as well as exact values in speci c cases.

Tripodoro J.C.V. , Golmohammadi H. , Chellali M.
Roman coalition partitions in graphs
Communications in Combinatorics and Optimization. 2026. DOI: 10.22049/cco.2026.30582.2542

Submitted:	May 2, 2025
Accepted:	Feb 7, 2026
Published online:	Apr 21, 2026

No identifiers