On Simultaneous 2-locally-balanced 2-partition for Two Forests with Same Vertices

Hovik G.  Tananyan; Rafayel R.  Kamalian

On Simultaneous 2-locally-balanced 2-partition for Two Forests with Same Vertices

Authors

Hovik G. Tananyan Russian-Armenian University
Rafayel R. Kamalian Yerevan State University

Abstract

The existence of a partition of the common set of the vertices of two forests into two subsets, when difference of their capacities in the neighbourhood of each vertex of each forest is not greater than 2 is proved, and an example, which shows that improvement of the specified constant is impossible is brought.

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, v. 105, N1, 2005, pp. 21-27. (In Russian.)

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, v. 106, N3, 2006, pp. 218-226. (In Russian.)

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

D. de Werra, Balanced Schedules, INFORJ., 9 (3), 1971, pp. 230-237.

Downloads

Published

2021-12-10

How to Cite

Tananyan, H. G. ., & Kamalian, R. R. . (2021). On Simultaneous 2-locally-balanced 2-partition for Two Forests with Same Vertices. Mathematical Problems of Computer Science, 29, 104–106. Retrieved from http://mpcs.sci.am/index.php/mpcs/article/view/453