کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4647413 1632420 2014 12 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Extremal values of ratios: Distance problems vs. subtree problems in trees II
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
Extremal values of ratios: Distance problems vs. subtree problems in trees II
چکیده انگلیسی
We discovered a dual behavior of two tree indices, the Wiener index and the number of subtrees, for a number of extremal problems (Székely and Wang, 2006, 2005). We introduced the concept of subtree core: the subtree core of a tree consists of one or two adjacent vertices of a tree that are contained in the largest number of subtrees. Let σ(T) denote the sum of distances between unordered pairs of vertices in a tree T and σT(v) the sum of distances from a vertex v to all other vertices in T. Barefoot et al. (1997) determined extremal values of σT(w)/σT(u), σT(w)/σT(v), σ(T)/σT(v), and σ(T)/σT(w), where T is a tree on n vertices, v is in the centroid of the tree T, and u,w are leaves in T. Let F(T) denote the number of subtrees of T and FT(v) the number of subtrees containing v in T. In Part I of this paper we tested how far the negative correlation between distances and subtrees go if we look for (and characterize) the extremal values of FT(w)/FT(u), FT(w)/FT(v). In this paper we characterize the extremal values of F(T)/FT(v), and F(T)/FT(w), where T is a tree on n vertices, v is in the subtree core of the tree T, and w is a leaf in T-completing the analogy, changing distances to the number of subtrees.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 322, 6 May 2014, Pages 36-47
نویسندگان
, ,