Geodesic
On locally-balanced $2$-partitions of some classes of graphs
Proceedings of the Yerevan State University. Physical and mathematical sciences, Tome 54 (2020) no. 1, pp. 9-19

Voir la notice de l'article provenant de la source Math-Net.Ru

In this paper we obtain some conditions for the existence of locally-balanced $2$-partitions with an open (with a closed) neighborhood of some classes of graphs. In particular, we give necessary conditions for the existence of locally-balanced $2$-partitions of even and odd graphs. We also obtain some results on the existence of locally-balanced $2$-partitions of rook's graphs and powers of cycles. In particular, we prove that if $m,n\geq 2$, then the graph $K_{m} \Box K_{n}$ has a locally-balanced $2$-partition with a closed neighborhood if and only if $m$ and $n$ are even. Moreover, all our proofs are constructive and provide polynomial time algorithms for constructing the required $2$-partitions.
Keywords: locally-balanced $2$-partition, equitable coloring, even (odd) graph, rook's graph, power of cycles. 
@article{UZERU_2020_54_1_a1,
     author = {A. G. Gharibyan},
     title = {On locally-balanced $2$-partitions of some classes of graphs},
     journal = {Proceedings of the Yerevan State University. Physical and mathematical sciences},
     pages = {9--19},
     publisher = {mathdoc},
     volume = {54},
     number = {1},
     year = {2020},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/UZERU_2020_54_1_a1/}
}
TY  - JOUR
AU  - A. G. Gharibyan
TI  - On locally-balanced $2$-partitions of some classes of graphs
JO  - Proceedings of the Yerevan State University. Physical and mathematical sciences
PY  - 2020
SP  - 9
EP  - 19
VL  - 54
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/UZERU_2020_54_1_a1/
LA  - en
ID  - UZERU_2020_54_1_a1
ER  - 
%0 Journal Article
%A A. G. Gharibyan
%T On locally-balanced $2$-partitions of some classes of graphs
%J Proceedings of the Yerevan State University. Physical and mathematical sciences
%D 2020
%P 9-19
%V 54
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/UZERU_2020_54_1_a1/
%G en
%F UZERU_2020_54_1_a1
A. G. Gharibyan. On locally-balanced $2$-partitions of some classes of graphs. Proceedings of the Yerevan State University. Physical and mathematical sciences, Tome 54 (2020) no. 1, pp. 9-19. http://geodesic.mathdoc.fr/item/UZERU_2020_54_1_a1/