Large butterfly Cayley graphs and digraphs

Research output: Contribution to journalArticle

Abstract

We present families of large undirected and directed Cayley graphs whose construction is related to butterfly networks. One approach yields, for every large k and for values of d taken from a large interval, the largest known Cayley graphs and digraphs of diameter k and degree d. Another method yields, for sufficiently large k and infinitely many values of d, Cayley graphs and digraphs of diameter k and degree d whose order is exponentially larger in k than any previously constructed. In the directed case, these are within a linear factor in k of the Moore bound.
LanguageEnglish
Pages2432-2436
Number of pages5
JournalDiscrete Mathematics
Volume340
Issue number10
Early online date24 Jun 2017
DOIs
StatePublished - 1 Oct 2017

Fingerprint

Cayley Digraph
Directed graphs
Cayley Graph
Directed Graph
Interval

Keywords

  • Cayley graphs
  • degree–diameter problem
  • butterfly networks
  • Moore bound

Cite this

Bevan, David. / Large butterfly Cayley graphs and digraphs. In: Discrete Mathematics. 2017 ; Vol. 340, No. 10. pp. 2432-2436
@article{8f3e791608b4463781a2153edba5abd6,
title = "Large butterfly Cayley graphs and digraphs",
abstract = "We present families of large undirected and directed Cayley graphs whose construction is related to butterfly networks. One approach yields, for every large k and for values of d taken from a large interval, the largest known Cayley graphs and digraphs of diameter k and degree d. Another method yields, for sufficiently large k and infinitely many values of d, Cayley graphs and digraphs of diameter k and degree d whose order is exponentially larger in k than any previously constructed. In the directed case, these are within a linear factor in k of the Moore bound.",
keywords = "Cayley graphs, degree–diameter problem, butterfly networks, Moore bound",
author = "David Bevan",
year = "2017",
month = "10",
day = "1",
doi = "10.1016/j.disc.2017.05.012",
language = "English",
volume = "340",
pages = "2432--2436",
journal = "Discrete Mathematics",
issn = "0012-365X",
number = "10",

}

Large butterfly Cayley graphs and digraphs. / Bevan, David.

In: Discrete Mathematics, Vol. 340, No. 10, 01.10.2017, p. 2432-2436.

Research output: Contribution to journalArticle

TY - JOUR

T1 - Large butterfly Cayley graphs and digraphs

AU - Bevan,David

PY - 2017/10/1

Y1 - 2017/10/1

N2 - We present families of large undirected and directed Cayley graphs whose construction is related to butterfly networks. One approach yields, for every large k and for values of d taken from a large interval, the largest known Cayley graphs and digraphs of diameter k and degree d. Another method yields, for sufficiently large k and infinitely many values of d, Cayley graphs and digraphs of diameter k and degree d whose order is exponentially larger in k than any previously constructed. In the directed case, these are within a linear factor in k of the Moore bound.

AB - We present families of large undirected and directed Cayley graphs whose construction is related to butterfly networks. One approach yields, for every large k and for values of d taken from a large interval, the largest known Cayley graphs and digraphs of diameter k and degree d. Another method yields, for sufficiently large k and infinitely many values of d, Cayley graphs and digraphs of diameter k and degree d whose order is exponentially larger in k than any previously constructed. In the directed case, these are within a linear factor in k of the Moore bound.

KW - Cayley graphs

KW - degree–diameter problem

KW - butterfly networks

KW - Moore bound

UR - http://www.sciencedirect.com/science/journal/aip/0012365X

U2 - 10.1016/j.disc.2017.05.012

DO - 10.1016/j.disc.2017.05.012

M3 - Article

VL - 340

SP - 2432

EP - 2436

JO - Discrete Mathematics

T2 - Discrete Mathematics

JF - Discrete Mathematics

SN - 0012-365X

IS - 10

ER -