A note on weighted rooted trees

作者：Song Zi Xia^*; Ward Talon; York Alexander

来源：Discrete Mathematics, 2015, 338(12): 2492-2494.

DOI：10.1016/j.disc.2015.06.014

• Rooted tree
• Weighted graph
• Path

Let T be a tree rooted at r. Two vertices of T are related if one is a descendant of the other; otherwise, they are unrelated. Two subsets A and B of V(T) are unrelated if, for any a is an element of A and b is an element of B, a and b are unrelated. Let omega be a nonnegative weight function defined on V (T) with Sigma(v is an element of V(T)) omega(v) = 1. In this note, we prove that either there is an (r, u)-path P with Sigma(v is an element of V(P)) omega(v) >= 1/3 for some u is an element of V(T), or there exist unrelated sets A, B subset of V(T) such that Sigma(a is an element of A) omega(a) >= 1/3 and Sigma(b is an element of B) omega(b) >= 1/3. The bound 1/3 is tight. This answers a question posed in a very recent paper of Bonamy, Bousquet and Thomasse.

• 出版日期2015-12-6