کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
6416506 1336829 2013 19 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Geometric aspects of 2-walk-regular graphs
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات اعداد جبر و تئوری
پیش نمایش صفحه اول مقاله
Geometric aspects of 2-walk-regular graphs
چکیده انگلیسی

A t-walk-regular graph is a graph for which the number of walks of given length between two vertices depends only on the distance between these two vertices, as long as this distance is at most t. Such graphs generalize distance-regular graphs and t-arc-transitive graphs. In this paper, we will focus on 1- and in particular 2-walk-regular graphs, and study analogues of certain results that are important for distance-regular graphs. We will generalize Delsarteʼs clique bound to 1-walk-regular graphs, Godsilʼs multiplicity bound and Terwilligerʼs analysis of the local structure to 2-walk-regular graphs. We will show that 2-walk-regular graphs have a much richer combinatorial structure than 1-walk-regular graphs, for example by proving that there are finitely many non-geometric 2-walk-regular graphs with given smallest eigenvalue and given diameter (a geometric graph is the point graph of a special partial linear space); a result that is analogous to a result on distance-regular graphs. Such a result does not hold for 1-walk-regular graphs, as our construction methods will show.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Linear Algebra and its Applications - Volume 439, Issue 9, 1 November 2013, Pages 2692-2710
نویسندگان
, , , ,