Cayley graphs of diameter two and any degree with order half of the Moore bound

It is well known that the number of vertices of a graph of diameter two and maximum degree dd is at most d2+1d2+1. The number d2+1d2+1 is the Moore bound for diameter two. Let C(d,2)C(d,2) denote the largest order of a Cayley graph of degree dd and diameter two. Up to now, the only known construction of Cayley graphs of diameter two valid for all degrees dd is a construction giving C(d,2)>14d2+d. However, there is a construction yielding Cayley graphs of diameter two, degree dd and order d2−O(d32) for an infinite set of degrees dd of a special type.In this article we present, for any integer d≥4d≥4, a construction of Cayley graphs of diameter two, degree dd and of order 12d2−t for dd even and of order 12(d2+d)−t for dd odd, where 0≤t≤80≤t≤8 is an integer depending on the congruence class of dd modulo 8.In addition, we show that, in asymptotic sense, the most of record Cayley graphs of diameter two is obtained by our construction.