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

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 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

2021-12-10

How to Cite

Balikyan, S. V. ., & Kamalian, R. R. . (2021). On Existence of 2-partition of a Tree, Which Obeys the Given Priority. Mathematical Problems of Computer Science, 30, 31–35. Retrieved from http://mpcs.sci.am/index.php/mpcs/article/view/412