pith. sign in

arxiv: 1506.05780 · v1 · pith:ZAVLJYQBnew · submitted 2015-06-18 · 🧮 math.CO

Cayley graphs of diameter two from difference sets

classification 🧮 math.CO
keywords fracgraphcayleydiameterlargeabeliandifferencegraphs
0
0 comments X
read the original abstract

Let $C(d,k)$ and $AC(d,k)$ be the largest order of a Cayley graph and a Cayley graph based on an abelian group, respectively, of degree $d$ and diameter $k$. When $k=2$, it is well-known that $C(d,2)\le d^2+1$ with equality if and only if the graph is a Moore graph. In the abelian case, we have $AC(d,2)\le \frac{d^2}{2}+d+1$. The best currently lower bound on $AC(d,2)$ is $\frac{3}{8}d^2-1.45 d^{1.525}$ for all sufficiently large $d$. In this paper, we consider the construction of large graphs of diameter $2$ using generalized difference sets. We show that $AC(d,2)\ge \frac{25}{64}d^2-2.1 d^{1.525}$ for sufficiently large $d$ and $AC(d,2) \ge \frac{4}{9}d^2$ if $d=3q$, $q=2^m$ and $m$ is odd.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.