Necessary and Sufficient Condition for Existence of Locally-balanced 2-partition of a Tree under the Extended Definition of a Neighbourhood of a Vertex
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.
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.