Roman coalition partitions in graphs | Sciact - Система учета научной деятельности ИМ СО РАН

Roman coalition partitions in graphs Научная публикация

Журнал

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

Вых. Данные

Год: 2026, DOI: 10.22049/cco.2026.30582.2542

Ключевые слова

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

Авторы

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

Организации

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

Информация о финансировании (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

Поступила в редакцию:	2 мая 2025 г.
Принята к публикации:	7 февр. 2026 г.
Опубликована online:	21 апр. 2026 г.

Нет идентификаторов