Abstract

In this paper we obtain some conditions for the existence of locally-balanced2-partitions with an open (with a closed) neighborhood of some classes ofgraphs. In particular, we give necessary conditions for the existence of locally-balanced 2-partitions of even and odd graphs. We also obtain some results onthe existence of locally-balanced 2-partitions of rook’s graphs and powers ofcycles. In particular, we prove that ifm,n≥2, then the graphKmKnhas alocally-balanced 2-partition with a closed neighborhood if and only ifmandnare even. Moreover, all our proofs are constructive and provide polynomialtime algorithms for constructing the required 2-partitions.

‹ 1 / ? › − 100% + Open in new tab Download Cite

Loading the full text…