|
Proceedings of the Yerevan State University, series Physical and Mathematical Sciences, 2020, Volume 54, Issue 1, Pages 9–19
(Mi uzeru698)
|
|
|
|
This article is cited in 2 scientific papers (total in 2 papers)
Mathematics
On locally-balanced 22-partitions of some classes of graphs
A. G. Gharibyan Yerevan State University
Abstract:
In this paper we obtain some conditions for the existence of locally-balanced 22-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 22-partitions of even and odd graphs. We also obtain some results on the existence of locally-balanced 22-partitions of rook's graphs and powers of cycles. In particular, we prove that if m,n≥2m,n≥2, then the graph Km□Kn 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.
Received: 10.02.2020 Revised: 21.02.2020 Accepted: 30.03.2020
Citation:
A. G. Gharibyan, “On locally-balanced 2-partitions of some classes of graphs”, Proceedings of the YSU, Physical and Mathematical Sciences, 54:1 (2020), 9–19
Linking options:
https://www.mathnet.ru/eng/uzeru698 https://www.mathnet.ru/eng/uzeru/v54/i1/p9
|
Statistics & downloads: |
Abstract page: | 91 | Full-text PDF : | 33 | References: | 25 |
|