On divisible design Cayley graphs

Abstract

Let v, k, b, a be integers such that v > k ≥ b ≥ a ≥ 0. A Deza graph with parameters (v, k, b, a) is a k-regular graph on v vertices in which the number of common neighbors of any two distinct vertices takes two values a or b (a ≤ b). A k-regular graph on v vertices is a divisible design graph with parameters (v, k, λ₁, λ₂, m, n) when its vertex set can be partitioned into m classes of size n, such that any two distinct vertices from the same class have λ₁ common neighbors, and any two vertices from different classes have λ₂ common neighbors. It is clear, that divisible design graphs are Deza graphs.

It is shown that divisible design Cayley graphs arise only by means of divisible difference sets relative to some subgroup. Construction of a special set in an affine group over a finite field is given and shown that this set is a divisible difference set and thus its development is a divisible design Cayley graph.