ON LOCALLY-BALANCED 2-PARTITIONS OF SOME CLASSESOF GRAPHS

Author(s)

ON LOCALLY-BALANCED 2-PARTITIONS OF SOME CLASSESOF GRAPHS Aram Gharibyan

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.

DOI: 10.46991/PYSU:A/2020.54.1.009 Physical and Mathematical Sciences, 54(1 (251) 9-19

Download PDF

Keywords

locally-balanced 2-partition, equitable coloring, even (odd)graph, rook’s graph, power of cycles.

Check for updates

Share

Contact admin with any questions, comments or concerns

[email protected]