کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
420226 683910 2010 6 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
On mean distance and girth
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
On mean distance and girth
چکیده انگلیسی

We bound the mean distance in a connected graph which is not a tree in terms of its order nn and its girth gg. On one hand, we show that the mean distance is at most n+13−g(g2−4)12n(n−1)−g(g−2)(n−g)2n(n−1) if gg is even and at most n+13−g(g2−1)12n(n−1)−(g−1)2(n−g)2n(n−1) if gg is odd. On the other hand, we prove that the mean distance is at least ng4(n−1) unless GG is an odd cycle. This resolves two conjectures of AutoGraphiX.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 158, Issue 17, 28 October 2010, Pages 1888–1893
نویسندگان
, ,