# On Existence of 2-partition of a Tree, Which Obeys the Given Priority

## 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, which, for a given function p : V (G) ! f¡1; 0; 1g with some special restriction, satisfies the condition

j¸(v) \ V1j ¡ j¸(v) \ V2j = p(v) ¢ (jfvg \ V1j ¡ jfvg \ V2j) 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*, 31–35. Retrieved from http://mpcs.sci.am/index.php/mpcs/article/view/412

## Issue

## Section

## License

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