A Note On Weighted Rooted Trees

Keywords

Path; Rooted tree; Weighted graph

Abstract

Abstract 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∈A and b∈B, a and b are unrelated. Let ω be a nonnegative weight function defined on V(T) with Σv∈V(T)ω(v)=1. In this note, we prove that either there is an (r,u)-path P with Σv∈V(P)ω(v)≥1/3 for some u∈V(T), or there exist unrelated sets A,B⊆V(T) such that Σa∈Aω(a)≥1/3 and Σb∈Bω(b)≥1/3. The bound 1/3 is tight. This answers a question posed in a very recent paper of Bonamy, Bousquet and Thomassé.

Publication Date

7-11-2015

Publication Title

Discrete Mathematics

Volume

338

Issue

12

Number of Pages

2492-2494

Document Type

Article

Personal Identifier

scopus

DOI Link

https://doi.org/10.1016/j.disc.2015.06.014

Socpus ID

84936850027 (Scopus)

Source API URL

https://api.elsevier.com/content/abstract/scopus_id/84936850027

This document is currently not available here.

Share

COinS