Large Cayley digraphs of given degree and diameter (Q658078): Difference between revisions

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.