Cayley Graphs of Diameter Two from Difference Sets |
| |
| Authors: | Alexander Pott Yue Zhou |
| |
| Institution: | 1. FACULTY OF MATHEMATICS, OTTO‐VON‐GUERICKE UNIVERSITY, MAGDEBURG, GERMANYContract grant sponsor: National Natural Science Foundation of China;2. Contract grant numbers: 11401579 and 11531002.;3. COLLEGE OF SCIENCE, NATIONAL UNIVERSITY OF DEFENSE TECHNOLOGY, CHANGSHA, CHINA;4. CURRENT ADDRESS: INSTITüT FüR MATHEMATIK, UNIVERSIT?T AUGSBURG, AUGSBURG, GERMANY |
| |
| Abstract: | Let  and  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  , it is well known that  with equality if and only if the graph is a Moore graph. In the abelian case, we have  . The best currently lower bound on  is  for all sufficiently large d. In this article, we consider the construction of large graphs of diameter 2 using generalized difference sets. We show that  for sufficiently large d and  if  ,  and m is odd. |
| |
| Keywords: | Cayley graph degree– diameter problem group |
|
|
and 
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 
, it is well known that 
with equality if and only if the graph is a Moore graph. In the abelian case, we have 
. The best currently lower bound on 
is 
for all sufficiently large d. In this article, we consider the construction of large graphs of diameter 2 using generalized difference sets. We show that 
for sufficiently large d and 
if 
, 
and m is odd.