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

Coalition graphs of connected domination partitions in subcubic graphs Научная публикация

Журнал

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

Вых. Данные

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

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

domination in graphs, coalition graph, subcubic graph

Авторы

Dobrynin Andrey A. ¹ , Glebov Aleksey N. ¹

Организации

1	Sobolev Institute of Mathematics

Информация о финансировании (1)

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

FWNF-2026-0011

A graph is subcubic if it is connected and its maximum vertex degree does not exceed 3. Two disjoint vertex subsets of a graph G form a connected coalition in G if neither of them is a connected dominating set but their union is a connected dominating set. A connected coalition partition of G is a partition of its vertices π(G), such that each set of π(G) is either a connected dominating set consisting of a single vertex or forms a coalition with some set of π(G). The formation of connected coalitions is described by a coalition graph whose vertices correspond to the sets of π, and two vertices are adjacent if and only if the corresponding sets form a coalition in G. We characterize all coalition graphs of subcubic graphs.

Dobrynin A.A. , Glebov A.N.
Coalition graphs of connected domination partitions in subcubic graphs
Communications in Combinatorics and Optimization. 2026. DOI: 10.22049/cco.2026.31013.2710

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

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