Geometric aspects of 2-walk-regular graphs

M. Camara Vallejo, E.R. van Dam, J.H. Koolen, J. Park

Research output: Contribution to journalArticleScientificpeer-review

249 Downloads (Pure)

Abstract

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.
Original languageEnglish
Pages (from-to)2692-2710
JournalLinear Algebra and its Applications
Volume439
Issue number9
Publication statusPublished - 2013

Fingerprint

Regular Graph
Walk
Distance-regular Graph
Graph in graph theory
Arc-transitive Graph
Geometric Graphs
Generalise
Smallest Eigenvalue
Local Structure
Linear Space
Clique
Multiplicity
Analogue
Partial

Cite this

Camara Vallejo, M., van Dam, E. R., Koolen, J. H., & Park, J. (2013). Geometric aspects of 2-walk-regular graphs. Linear Algebra and its Applications, 439(9), 2692-2710.
Camara Vallejo, M. ; van Dam, E.R. ; Koolen, J.H. ; Park, J. / Geometric aspects of 2-walk-regular graphs. In: Linear Algebra and its Applications. 2013 ; Vol. 439, No. 9. pp. 2692-2710.
@article{8a8dce919aff47b5b6cd2d18bbe226e7,
title = "Geometric aspects of 2-walk-regular graphs",
abstract = "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.",
author = "{Camara Vallejo}, M. and {van Dam}, E.R. and J.H. Koolen and J. Park",
year = "2013",
language = "English",
volume = "439",
pages = "2692--2710",
journal = "Linear Algebra and its Applications",
issn = "0024-3795",
publisher = "Elsevier Inc.",
number = "9",

}

Camara Vallejo, M, van Dam, ER, Koolen, JH & Park, J 2013, 'Geometric aspects of 2-walk-regular graphs' Linear Algebra and its Applications, vol. 439, no. 9, pp. 2692-2710.

Geometric aspects of 2-walk-regular graphs. / Camara Vallejo, M.; van Dam, E.R.; Koolen, J.H.; Park, J.

In: Linear Algebra and its Applications, Vol. 439, No. 9, 2013, p. 2692-2710.

Research output: Contribution to journalArticleScientificpeer-review

TY - JOUR

T1 - Geometric aspects of 2-walk-regular graphs

AU - Camara Vallejo, M.

AU - van Dam, E.R.

AU - Koolen, J.H.

AU - Park, J.

PY - 2013

Y1 - 2013

N2 - 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.

AB - 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.

M3 - Article

VL - 439

SP - 2692

EP - 2710

JO - Linear Algebra and its Applications

JF - Linear Algebra and its Applications

SN - 0024-3795

IS - 9

ER -

Camara Vallejo M, van Dam ER, Koolen JH, Park J. Geometric aspects of 2-walk-regular graphs. Linear Algebra and its Applications. 2013;439(9):2692-2710.