On Existence of 2-partition of a Tree, Which Obeys the Given Priority
Suren V. Balikyan, Rafayel R. Kamalian · Mathematical Problems of Computer Science · 2008
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) ! fi1; 0; 1g with some special restriction, satisfies the conditionj¸(v) V1j i j¸(v) V2j = p(v) ¢ (jfvg V1j i jfvg V2j) for any vertex v of G, where¸(v) is the set of all vertices of G adjacent to v.