کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4646698 1342309 2016 6 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
A generalization of the odd-girth theorem
ترجمه فارسی عنوان
تعمیم قضیه odd-girth
کلمات کلیدی
فاصله منظم نمودار؛ تعمیم نمودار عجیب و غریب؛ مقادیر ویژه نمودار؛ عجیب و غریب؛ تئوری عظیم طیفی
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
چکیده انگلیسی

Let GG be a connected graph and MM be a non-negative symmetric matrix whose rows and columns can be indexed by the vertex set of GG such that for every two vertices u,vu,v, the (u,v)(u,v)-entry of MM is non-zero if and only if uu and vv are adjacent. It is well known that if dd is the diameter of GG, then MM has at least d+1d+1 distinct eigenvalues as well as the odd-girth of GG is at most 2d+12d+1. We prove that if MM has d+1d+1 distinct eigenvalues and the odd-girth of GG is 2d+12d+1, then GG must be a generalized odd graph and MM must be a scalar multiple of the adjacency matrix of GG. This generalizes a recent result that is called the ‘odd-girth theorem’. The proof is based on a generalization of the so-called ‘spectral excess theorem’.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 339, Issue 2, 6 February 2016, Pages 1052–1057
نویسندگان
,