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
Issue
Section
License
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.
