کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4650153 | 1342477 | 2009 | 9 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Bounds on isoperimetric values of trees
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
The depth d of a tree is the number of nodes on the longest path starting from the root and ending at a leaf. In this paper we show that for a complete binary tree of depth d (denoted as Td2), c1dâ¤be(Td2)â¤d and c2dâ¤bv(Td2)â¤d where c1, c2 are constants. For a complete t-ary tree of depth d (denoted as Tdt) and dâ¥clogt where c is a constant, we show that c1tdâ¤be(Tdt)â¤td and c2dtâ¤bv(Tdt)â¤d where c1, c2 are constants. At the heart of our proof we have the following theorem which works for an arbitrary rooted tree and not just for a complete t-ary tree. Let T=(V,E,r) be a finite, connected and rooted tree - the root being the vertex r. Define a weight function w:VâN where the weight w(u) of a vertex u is the number of its successors (including itself) and let the weight index η(T) be defined as the number of distinct weights in the tree, i.e η(T)=|{w(u):uâV}|. For a positive integer k, let â(k)=|{iâN:1â¤iâ¤|V|,be(i,G)â¤k}|. We show that â(k)â¤22η+kk.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 309, Issue 4, 6 March 2009, Pages 834-842
Journal: Discrete Mathematics - Volume 309, Issue 4, 6 March 2009, Pages 834-842
نویسندگان
B.V. Subramanya Bharadwaj, L. Sunil Chandran,