Distance-regular Cayley graphs with small valency

Edwin van Dam, Mojtaba Jazaeri

Research output: Contribution to journalArticleScientificpeer-review

Abstract

We consider the problem of which distance-regular graphs with small valency are Cayley graphs. We determine the distance-regular Cayley graphs with valency at most 4, the Cayley graphs among the distance-regular graphs with known putative intersection arrays for valency 5, and the Cayley graphs among all distance-regular graphs with girth 3 and valency 6 or 7. We obtain that the incidence graphs of Desarguesian affine planes minus a parallel class of lines are Cayley graphs. We show that the incidence graphs of the known generalized hexagons are not Cayley graphs, and neither are some other distance-regular graphs that come from small generalized quadrangles or hexagons. Among some “exceptional” distance-regular graphs with small valency, we find that the Armanios-Wells graph and the Klein graph are Cayley graphs.
Original languageEnglish
Pages (from-to)203-222
JournalArs Mathematica Contemporanea
Volume17
Issue number1
DOIs
Publication statusPublished - 2019

Fingerprint

Distance-regular Graph
Cayley Graph
Generalized Hexagon
Graph in graph theory
Incidence
Generalized Quadrangle
Affine plane
Girth
Intersection
Line

Keywords

  • Cayley graph
  • distance-regular graph

Cite this

van Dam, Edwin ; Jazaeri, Mojtaba. / Distance-regular Cayley graphs with small valency. In: Ars Mathematica Contemporanea. 2019 ; Vol. 17, No. 1. pp. 203-222.
@article{9ffe6f8f863b48b6879f30ae7a834c49,
title = "Distance-regular Cayley graphs with small valency",
abstract = "We consider the problem of which distance-regular graphs with small valency are Cayley graphs. We determine the distance-regular Cayley graphs with valency at most 4, the Cayley graphs among the distance-regular graphs with known putative intersection arrays for valency 5, and the Cayley graphs among all distance-regular graphs with girth 3 and valency 6 or 7. We obtain that the incidence graphs of Desarguesian affine planes minus a parallel class of lines are Cayley graphs. We show that the incidence graphs of the known generalized hexagons are not Cayley graphs, and neither are some other distance-regular graphs that come from small generalized quadrangles or hexagons. Among some “exceptional” distance-regular graphs with small valency, we find that the Armanios-Wells graph and the Klein graph are Cayley graphs.",
keywords = "Cayley graph, distance-regular graph",
author = "{van Dam}, Edwin and Mojtaba Jazaeri",
year = "2019",
doi = "10.26493/1855-3974.1964.297",
language = "English",
volume = "17",
pages = "203--222",
journal = "Ars Mathematica Contemporanea",
issn = "1855-3974",
number = "1",

}

Distance-regular Cayley graphs with small valency. / van Dam, Edwin; Jazaeri, Mojtaba.

In: Ars Mathematica Contemporanea, Vol. 17, No. 1, 2019, p. 203-222.

Research output: Contribution to journalArticleScientificpeer-review

TY - JOUR

T1 - Distance-regular Cayley graphs with small valency

AU - van Dam, Edwin

AU - Jazaeri, Mojtaba

PY - 2019

Y1 - 2019

N2 - We consider the problem of which distance-regular graphs with small valency are Cayley graphs. We determine the distance-regular Cayley graphs with valency at most 4, the Cayley graphs among the distance-regular graphs with known putative intersection arrays for valency 5, and the Cayley graphs among all distance-regular graphs with girth 3 and valency 6 or 7. We obtain that the incidence graphs of Desarguesian affine planes minus a parallel class of lines are Cayley graphs. We show that the incidence graphs of the known generalized hexagons are not Cayley graphs, and neither are some other distance-regular graphs that come from small generalized quadrangles or hexagons. Among some “exceptional” distance-regular graphs with small valency, we find that the Armanios-Wells graph and the Klein graph are Cayley graphs.

AB - We consider the problem of which distance-regular graphs with small valency are Cayley graphs. We determine the distance-regular Cayley graphs with valency at most 4, the Cayley graphs among the distance-regular graphs with known putative intersection arrays for valency 5, and the Cayley graphs among all distance-regular graphs with girth 3 and valency 6 or 7. We obtain that the incidence graphs of Desarguesian affine planes minus a parallel class of lines are Cayley graphs. We show that the incidence graphs of the known generalized hexagons are not Cayley graphs, and neither are some other distance-regular graphs that come from small generalized quadrangles or hexagons. Among some “exceptional” distance-regular graphs with small valency, we find that the Armanios-Wells graph and the Klein graph are Cayley graphs.

KW - Cayley graph

KW - distance-regular graph

U2 - 10.26493/1855-3974.1964.297

DO - 10.26493/1855-3974.1964.297

M3 - Article

VL - 17

SP - 203

EP - 222

JO - Ars Mathematica Contemporanea

JF - Ars Mathematica Contemporanea

SN - 1855-3974

IS - 1

ER -