Abstract:
A regular graph $\Gamma$ is called a Deza graph if there exist nonnegative integers $a$ and $b$ such that any two distinct vertices of $\Gamma$ have either $a$ or $b$ common neighbors. A subset $R$ of a group $G$ is called a relative difference set in $G$ if there exist a subgroup $N$ of $G$ and a nonnegative integer $\lambda$ such that every element of $G\setminus N$ has exactly $\lambda$ representations in the form $g_1g_2^{-1}$, where $g_1,g_2\in R$, and no non-identity element of $N$ has such a representation. If $N$ is trivial, then $R$ is defined to be a difference set. In the present paper, we provide several new constructions of Deza Cayley graphs over groups having a generalized dihedral subgroup. These constructions are based on usage of (relative) difference sets.
Fulltext:
PDF file (208 kB)
First page:
PDF file