Large butterfly Cayley graphs and digraphs

DOI10.1016/J.DISC.2017.05.012zbMATH Open1367.05099arXiv1507.08926OpenAlexW2614397974MaRDI QIDQ2012530FDOQ2012530

Authors: David Bevan 

Publication date: 1 August 2017

Published in: Discrete Mathematics (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/1507.08926

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

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)

Cites Work

• Title not available (Why is that?)
• Large Cayley graphs and vertex-transitive non-Cayley graphs of given degree and diameter
• Group Action Graphs and Parallel Architectures
• Cayley graphs of given degree and diameter for cyclic, Abelian, and metacyclic groups
• Large Cayley digraphs and bipartite Cayley digraphs of odd diameters
• Large Cayley digraphs 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)