ON LOCALLY-BALANCED 2-PARTITIONS OF SOME CLASSES OF GRAPHS

Abstract

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 \geq 2\), then the graph \(K_m \Box 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.