On divisible design Cayley graphs

Keywords: Deza graph, divisible design graph, divisible design, divisible different set, Cayley graph, affine group over a finite field

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, λ1, λ2, 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 λ1 common neighbors, and any two vertices from different classes have λ2 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.

Published
2020-02-19
Section
Groups and Graphs, Designs and Dynamics 2019