کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4649862 1342467 2009 5 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Average distance in graphs and eigenvalues
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
Average distance in graphs and eigenvalues
چکیده انگلیسی

Brendan McKay gave the following formula relating the average distance between pairs of vertices in a tree TT and the eigenvalues of its Laplacian: d¯T=2n−1∑i=2n1λi. By modifying Mohar’s proof of this result, we prove that for any graph GG, its average distance, d¯G, between pairs of vertices satisfies the following inequality: d¯G≥2n−1∑i=2n1λi. This solves a conjecture of Graffiti  . We also present a generalization of this result to the average of suitably defined distances for kk subsets of a graph.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 309, Issue 10, 28 May 2009, Pages 3458–3462
نویسندگان
,