کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
1708139 | 1012813 | 2012 | 4 صفحه PDF | دانلود رایگان |
In this note, we use a technique introduced by Dankelmann and Entringer [P. Dankelmann, R.C. Entringer, Average distance, minimum degree and spanning trees, J. Graph Theory 33 (2000) 1–13] to obtain a strengthening of an old classical theorem by Erdős, Pach, Pollack and Tuza [P. Erdős, J. Pach, R. Pollack, Z. Tuza, Radius, diameter, and minimum degree, J. Combin. Theory B 47 (1989) 73–79] on diameter and minimum degree. To be precise, we will prove that if GG is a connected graph of order nn and minimum degree δδ, then its diameter does not exceed 3(n−t)δ+1+O(1), where tt is the number of distinct terms of the degree sequence of GG. The featured parameter, tt, is attractive in nature and promising; more discoveries on it in relation to other graph parameters are envisaged.
Journal: Applied Mathematics Letters - Volume 25, Issue 2, February 2012, Pages 175–178