ON LOCALLY-BALANCED 2-PARTITIONS OF SOME CLASSESOF GRAPHS

This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

Submitted: 2025-01-29; Published: 2025-01-29

This work is licensed under Creative Commons Attribution–NonCommercial International License (CC BY-NC 4.0).

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.