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.
No institution available
Mathematics
, 2025, Issue 1, pp. 1–10
ISSN Online: 0000-0000
DOI:
10.xxxx/example-doi