On locally-balanced $2$-partitions of some classes of graphs

В настоящей работе даются необходимые и достаточные условия существования локально-сбалансированных $2$-разбиенией с открытой (закрытой) окрестностью для некоторых классов графов. В частности, в работе даны необходимые условия существования локально-сбалансированных $2$-разбиенией четных и нечетных графов. В работе также получены некоторые результаты существования локально-сбалансированных $2$-разбиенией ладейных графов и различных степеней цикла. В частности, в работе доказано, что если $m, n\geq 2$, то ладейный граф $K_{m} \Box K_{n}$ имеет локально-сбалансированное $2$-разбиение с закрытой окрестностью тогда и только тогда, когда $m$ и $n$ — четные числа. Кроме того, все предложенные доказательства являются конструктивные, и строят требуемые $2$-разбиения с помощью полиномиальных алгоритмов.