Necessary and Sufficient Condition for Existence of Locally-balanced 2-partition of a Tree under the Extended Definition of a Neighbourhood of a Vertex

Suren V.  Balikyan; Rafayel R.  Kamalian

Necessary and Sufficient Condition for Existence of Locally-balanced 2-partition of a Tree under the Extended Definition of a Neighbourhood of a Vertex

Authors

Suren V. Balikyan Yerevan State University
Rafayel R. Kamalian Russian-Armenian University

Abstract

A necessary and sufficient condition is obtained for the problem of partitioning of the set of vertices of a tree G into two disjoint sets V1 and V2 such that it satisfies the condition ||λ(v \ V1|–|λ( v) \ V2|| ≤ 1 for any vertex v of G, where λ(v) is the set of all vertices of G the distance of which from v does not exceed 1.

References

S.V. Balikyan, R.R.Kamalian, "On NP-completeness of the Problem of Existence of Locally-balanced 2-partition for Bipartite Graphs G with Δ(G)=3", Reports of NAS RA, vol. 105, num. 1, pp. 21-27, 2005.

S.V. Balikyan, R.R. Kamalian, "On NP-completeness of the Problem of Existence of Locally-balanced 2-partition for Bipartite Graphs G with Δ(G)=4 under the Extended Definition of the Neighbourhood of a Vertex", Reports of NAS RA, vol. 106, num. 3, pp. 218-226, 2006.

S.V. Balikyan, "On Locally-balanced 2-partitions of some Bipartite Graphs", Abstracts of papers of 15th International Conference "Mathematics. Computing. Education.", vol. 15, p. 7, Dubna, Russia, January 28-February 02 2008.

F. Harary, Graph Theory, Addison-Wesley, Reading, MA, 1969.

C. Berge, Graphs and Hypergraphs, Elsevier Science Ltd, 1985.

Downloads

Published

2021-12-10

How to Cite

Balikyan , S. V. ., & Kamalian, . R. R. . (2021). Necessary and Sufficient Condition for Existence of Locally-balanced 2-partition of a Tree under the Extended Definition of a Neighbourhood of a Vertex. Mathematical Problems of Computer Science, 31, 116–121. Retrieved from http://mpcs.sci.am/index.php/mpcs/article/view/398