Large butterfly Cayley graphs and digraphs

DOI10.1016/J.DISC.2017.05.012MaRDI QIDQ2012530zbMATH OpenOpenAlexFDO

Authors David Bevan

Publication date 1 August 2017

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1507.08926, https://strathprints.strath.ac.uk/60775/1/Bevan_DM_2017_Large_butterfly_Cayley_graphs_and_digraphs.pdf

zbMATH Keywords

Cayley graphbutterfly networkdegree-diameter problem

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Small world graphs, complex networks (graph-theoretic aspects) (05C82) Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Structural characterization of families of graphs (05C75)

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.

Recommendations

• Large Cayley digraphs of given degree and diameter
• A note on a geometric construction of large Cayley graphs of given degree and diameter
• Large Cayley digraphs and bipartite Cayley digraphs of odd diameters
• Large Cayley graphs and vertex-transitive non-Cayley graphs of given degree and diameter
• Cayley graphs of given degree and diameters 3, 4 and 5

Cites work

• scientific article; zbMATH DE number 3095523 (Why is no real title available?)
• Cayley graphs of given degree and diameter for cyclic, Abelian, and metacyclic groups
• Group Action Graphs and Parallel Architectures
• Large Cayley digraphs and bipartite Cayley digraphs of odd diameters
• Large Cayley digraphs of given degree and diameter
• Large Cayley graphs and vertex-transitive non-Cayley graphs of given degree and diameter

Cited in

(9)

• Large Cayley graphs of small diameter
• Large vertex symmetric digraphs
• Abelian Cayley digraphs with asymptotically large order for any given degree
• Revisiting the Comellas-Fiol-Gómez constructions of large digraphs of given degree and diameter
• Representations of Borel Cayley Graphs
• Large Cayley digraphs and bipartite Cayley digraphs of odd diameters
• The Cayley graphs of Burnside groups of exponent 3.
• Large Cayley digraphs of given degree and diameter from sharply \(t\)-transitive groups
• Which Faber-Moore-Chen digraphs are Cayley digraphs?

This page was built for publication: Large butterfly Cayley graphs and digraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2012530)