# On Existence of Certain Locally-balanced 2-partition of a Tree

## Abstract

A necessary and sufficient condition is obtained for the problem of such partitioning of the set of vertices of a tree G into two disjoint sets V1 and V2, such that for given sets V 0 1 μ V (G) and V 0

2 μ V (G) (V 0 1 \ V 0 2 = ;) it satis¯es the conditions V 0 1 μ V1, V 0 2 μ V2 and jj¸(v) \ V1j¡j¸(v) \ V2jj · 1 for any vertex v of G, where ¸(v) is the set of all vertices of G adjacent to v.

## 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, Applied Mathematics, 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, Applied Mathematics, 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

## How to Cite

*Mathematical Problems of Computer Science*,

*30*, 25–30. Retrieved from http://mpcs.sci.am/index.php/mpcs/article/view/411

## Issue

## Section

## License

This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.