|
Mathematics
Locally-balanced $k$-partitions of graphs
[Локально-сбалансированные $k$-разбиения графов]
A. H. Gharibyan, P. A. Petrosyan Yerevan State University, Faculty of Informatics and Applied Mathematics
Аннотация:
В работе обобщены локально-сбалансированные $2$-разбиения графов и введено новое понятие – локально сбалансированные $k$-разбиения графов, определяемые следующим образом: сюръекция $f:V(G)\rightarrow \{0,1,...,k-1\}$ называется $k$-разбиением графа $G$. $k$-Разбиение ($k \geq 2$) $f$ графа $G$ является локально-сбалансированным с открытой окрестностью, если для любой вершины $v \in V(G)$ и любых $ 0 \leq i <j \leq k-1$
$$\left\vert \vert \{u\in N_{G}(v)\colon\,f(u)=i\}\vert - \vert
\{u\in N_{G}(v)\colon\,f(u)=j\}\vert \right\vert\leq 1.$$
$k$-Разбиение ($k \geq 2$) $f^{\prime}$ графа $G$ является локально-сбалансированным с закрытой окрестностью, если для любой вершины $v \in V(G)$ и любых $ 0 \leq i <j \leq k-1$
$$\left\vert \vert \{u\in N_{G}[v]\colon\,f^{\prime}(u)=i\}\vert - \vert \{u\in N_{G}[v]\colon\,f^{\prime}(u)=j\}\vert \right\vert\leq 1.$$
Mинимальное число $k$ ($ k \geq 2$), для которого граф $G$ имеет локально-сбалансированное $k$-разбиение с открытой (закрытой) окрестностью, называется $lb$-открытым ($lb$-закрытым) хроматическим числом $G$ и обозначается через $\chi_{(lb)}(G)$ ($\chi_{[lb]}(G)$). В работе даны оценки или определены точные значения $lb$-открытого и $lb$-закрытого хроматических чисел некоторых классов графов. Кроме того, рассмотрены связи $lb$-открытых и $lb$-закрытых хроматических чисел графов с другими хроматическими числами, такими как инъективные и $2$-дистанционные хроматические числа.
Ключевые слова:
$2$-partition, $k$-partition, locally-balanced $k$-partition, complete graph, bipartite graph.
Поступила в редакцию: 25.02.2021 Исправленный вариант: 18.05.2021 Принята в печать: 01.06.2021
Образец цитирования:
A. H. Gharibyan, P. A. Petrosyan, “Locally-balanced $k$-partitions of graphs”, Уч. записки ЕГУ, сер. Физика и Математика, 55:2 (2021), 96–112
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/uzeru837 https://www.mathnet.ru/rus/uzeru/v55/i2/p96
|
Статистика просмотров: |
Страница аннотации: | 89 | PDF полного текста: | 24 | Список литературы: | 11 |
|