| Abelian Cayley graphs are important research objects in the study of algebraic graph theory.They also have strong connections with coding theory and cryptography.For a given valency and a given diameter,there is an upper bound on the cardinality of the vertex set of an abelian Cayley graph.We call it the abelian-Cayley-Moore bound,and the graphs meeting this bound abelian-Cayley-Moore graphs.The classification of abelianCayley-Moore graphs plays a central role in the study of Degree/Diameter problems of graph theory,and it also corresponds to the existence problem of linear perfect Lee codes which is important in coding theory.In particular,when the diameter of the graph equals 2 and the valency is 2n,an abelian-Cayley-Moore graph has exactly 2n2+2n+1 vertices,for which the classification has been recently o btained.Based on the results,we mainly investigate abelian Cayley graphs whose numbers of vertices differ from 2n2+2n+1 by 1,and the related coding theory problems.Precisely speaking,they are:1)Abelian Cayley graphs of degree 2n and diameter 2 with exactly 2n2+2n vertices;2)Abelian Cayley graphs of degree 2n and diameter 3 whose order is 2n2+2n+2 such that their generating set denoted by S satisfies |S2|=2n2+2n+1 where S=S ∪{e};3)The abelian Cayley graphs of degree d and diameter k whose vertex set consists of∑i=0 k(id)elements of order 2.For the first two types of graphs,by applying various tools from algebraic number theory,finite fields,characters of groups,symmetric polynomials,etc.,we show their nonexistence under certain elementary number theoretic conditions on n.According to these results,we calculate the number of values of n within 105 in which the first two types of graphs do not exist by computer programs.For the last type of graphs,we prove that they are equivalent to binary linear perfect codes under the Hamming-metric.By the known results on the classification of perfect codes,we present a complete classification of the third type of graphs. |
PDF Full Text Request