Large Cayley digraphs and bipartite Cayley digraphs of odd diameters

Abstract

Let $C_{d,k}$ be the largest number of vertices in a Cayley digraph of degree $d$ and diameter $k$, and let $B{C}_{d,k}$ be the largest order of a bipartite Cayley digraph for given $d$ and $k$. For every degree $d\ge 2$ and for every odd $k$ we construct Cayley digraphs of order $2k{\left(\lfloor \frac{d}{2}\rfloor \right)}^k$ and diameter at most $k$, where $k\ge 3$, and bipartite Cayley digraphs of order $2(k-1){\left(\lfloor \frac{d}{2}\rfloor \right)}^{k-1}$ and diameter at most $k$, where $k\ge 5$. These constructions yield the bounds $C_{d,k}\ge 2k{\left(\lfloor \frac{d}{2}\rfloor \right)}^k$ for odd $k\ge 3$ and $d\ge \frac{3^k}{2k}+1$, and $B{C}_{d,k}\ge 2(k-1){\left(\lfloor \frac{d}{2}\rfloor \right)}^{k-1}$ for odd $k\ge 5$ and $d\ge \frac{3^{k-1}}{k-1}+1$. Our constructions give the best currently known bounds on the orders of large Cayley digraphs and bipartite Cayley digraphs of given degree and odd diameter $k\ge 5$. In our proofs we use new techniques based on properties of group automorphisms of direct products of abelian groups.

arXiv comment16 pages, Published in Discrete Mathematics. Free access to the article valid until May 09, 2017: http://doi.org/10.1016/j.disc.2017.02.005