2020; Physical and Mathematical Sciences, 54(1 (251): 9–19
Shared with The Gufo

ON LOCALLY-BALANCED 2-PARTITIONS OF SOME CLASSESOF GRAPHS

Received: 2025-01-29 · Published: 2020-04-15

Shared article.
Original title
ON LOCALLY-BALANCED 2-PARTITIONS OF SOME CLASSESOF GRAPHS
Author
Aram Gharibyan
Published
2020-04-15
Licence
Creative Commons Attribution-NonCommercial 4.0 International
Original
https://doi.org/10.46991/PYSU:A/2020.54.1.009

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…

Download Follow Updates