|
Эта публикация цитируется в 1 научной статье (всего в 1 статье)
Mathematics
On locally-balanced 2-partitions of bipartite graphs
[О локально-сбалансированных 2-разбиениях двудольных графов]
A. H. Gharibyan, P. A. Petrosyan Yerevan State University, Faculty of Informatics and Applied Mathematics
Аннотация:
$2$-Разбиением графа $g$ называется функция $f:v(g)\rightarrow\{0,1\}$. $2$-Разбиение $f$ графа $g$ называется локально-сбалансированным с открытой окрестностью, если для любой вершины $v\in v(g),$ $\big||\{u\in n_g (v):f(u)=0\}|-|\{u\in n_g (v):f(u)=1\}|\big| \leq 1$. Двудольный граф называется $(a,b)$-бирегулярным, если все вершины одной доли имеют степень $a$, а все вершины другой доли имеют степень $b$. В настоящей работе доказано, что задача существo вания локально-сбалансированных $2$-разбиений с открытой окрестностью $np$-полна даже в случае $(3,8)$-бирегулярных двудольных графов. Также доказано, что $(2,2k+1)$-бирегулярный двудольный граф имеет локально-сбалансированное $2$-разбиение с открытой окрестностью тогда и только тогда, когда он не содержит простой цикл длины $2 (\mathrm{mod}~4)$. Кроме того, в работе доказано, что если субкубический двудольный граф $g$ не содержит простых циклов длины $2 (\mathrm{mod}~4)$, то он имеет локально-сбалансированное $2$-разбиение с открытой окрестностью. В конце работы показано, что все двояковыпуклые двудольные графы имеют локально-сбалансированное $2$-разбиение с открытой окрестностью.
Ключевые слова:
locally-balanced $2$-partition, NP-completeness, bipartite graph, biregular bipartite graph, subcubic bipartite graph.
Поступила в редакцию: 02.10.2020 Исправленный вариант: 15.12.2020 Принята в печать: 18.12.2020
Образец цитирования:
A. H. Gharibyan, P. A. Petrosyan, “On locally-balanced 2-partitions of bipartite graphs”, Уч. записки ЕГУ, сер. Физика и Математика, 54:3 (2020), 137–145
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/uzeru751 https://www.mathnet.ru/rus/uzeru/v54/i3/p137
|
Статистика просмотров: |
Страница аннотации: | 140 | PDF полного текста: | 18 | Список литературы: | 12 |
|