Cayley graphs of diameter two from difference sets

2015/06/18 by Alexander Pott, Yue Zhou, Pott, Alexander +1
Computer Science · Engineering · Mathematics · #Coding theory and cryptography #Combinatorics (math.CO) #FOS: Mathematics #Finite Group Theory Research #graph theory and CDMA systems #math.CO

paper · pdf · doi:10.48550/arxiv.1506.05780

arxiv created 2015/06/18 · openalex publication_date 2015/06/18 · arxiv updated 2015/06/19 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

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)≤ d²+1 with equality if and only if the graph is a Moore graph. In the abelian case, we have AC(d,2)≤ (d²)/(2)+d+1. The best currently lower bound on AC(d,2) is (3)/(8)d²-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)≥ (25)/(64)d²-2.1 d^1.525 for sufficiently large d and AC(d,2) ≥ (4)/(9)d² if d=3q, q=2^m and m is odd.

Related

• Improved upper bounds for the order of some classes of Abelian Cayley and circulant graphs of diameter two
• Large Cayley graphs of small diameter
• Asymptotically approaching the Moore bound for diameter three by Cayley\n graphs
• An improved Moore bound and some new optimal families of mixed Abelian Cayley graphs
• New large graphs with given degree and diameter