Large Cayley digraphs of given degree and diameter
type: Item
instance of: scholarly article
title: Large Cayley digraphs of given degree and diameter
zbMATH Open document ID: 1251.05067
author: Tomáš Vetrík
published in: Discrete Mathematics
publication date: 2012-01-11T00:00:00Z
review text: In this paper, the author attacks the degree-diameter problem for Cayley digraphs and bipartite Cayley digraphs. The problem is to determine the largest order of digraphs (i.e., directed graphs) of given maximum degree and diameter. For any \(d\geq 4\) and \(k\geq 3\), the author constructs a family of Cayley digraphs of degree \(d\), diameter \(k\) and order \(k[\frac{d}{2}]^k\). For sufficiently large \(d\) and \(k\) with \(k\not\in\{d,d-1\}\), the constructed digraphs are the largest known Cayley digraphs (of degree \(d\) and diameter \(k\)). For any degree \(d\geq 4\) and diameter \(k\geq 4\), the author also presents a class of bipartite Cayley digraphs of order at least \((k-1)[\frac{d}{2}]^{k-1}\), which are also the largest known Cayley digraphs (of degree \(d\) and diameter \(k\)) when \(d\) and \(k\) are sufficiently large.
Mathematics Subject Classification ID: 05C20
Mathematics Subject Classification ID: 05C25
Mathematics Subject Classification ID: 05C12
zbMATH DE Number: 5996517
zbMATH Keywords: Cayley digraph
zbMATH Keywords: Bipartite digraph
zbMATH Keywords: Vertex degree
zbMATH Keywords: Diameter
reviewed by: Tongsuo Wu
MaRDI profile type: Publication
full work available at URL: j.disc.2011.09.011
OpenAlex ID: W1995336971
cites work: Q4298684
cites work: The Degree-Diameter Problem for Several Varieties of Cayley Graphs I: The Abelian Case
cites work: Cycle prefix digraphs for symmetric interconnection networks
cites work: Large Cayley graphs on an abelian group
cites work: Q4842420
cites work: Large Cayley graphs and vertex-transitive non-Cayley graphs of given degree and diameter
cites work: Moore graphs and beyond: a survey of the degree/diameter problem
cites work: Large bipartite Cayley graphs of given degree and diameter
cites work: Which Faber-Moore-Chen digraphs are Cayley digraphs?
DOI: 10.1016/J.DISC.2011.09.011
Recommended article: Q4842420
Recommended article: Large bipartite Cayley graphs of given degree and diameter
Recommended article: Large Cayley digraphs and bipartite Cayley digraphs of odd diameters
Recommended article: A note on large Cayley graphs of diameter two and given degree
Recommended article: Large Cayley graphs of small diameter
Recommended article: Large vertex-transitive and Cayley graphs with given degree and diameter
Recommended article: Q3836332
Recommended article: The diameters of almost all Cayley digraphs
Recommended article: Large Cayley graphs and vertex-transitive non-Cayley graphs of given degree and diameter
description: scientific article; zbMATH DE number 5996517