ON LOCALLY-BALANCED 2-PARTITIONS OF SOME CLASSES OF GRAPHS - Gharibyan, A.H. (Proceedings of the YSU A: Physical and Mathematical Sciences, 2020)
In this paper we obtain some conditions for the existence of locally-balanced 2-partitions with an open (with a closed) neighborhood of some classes of graphs. In particular, we give necessary conditions for the existence of locallybalanced 2-partitions of even and odd graphs. We also obtain some results on the existence of locally-balanced 2-partitions of rook’s graphs and powers of cycles. In particular, we prove that if \(m,n ≥ 2\), then the graph \(K_m K_n\) has a locally-balanced 2-partition with a closed neighborhood if and only if m and n are even. Moreover, all our proofs are constructive and provide polynomial time algorithms for constructing the required 2-partitions.