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