Le Anh Vinh
Finite Euclidean Graphs over $\mathbbm{Z}_{2^r}$ are Non--Ramanujan
Preprint series: ESI preprints

MSC:

05C35 Extremal problems, See also {90C35}

05C38 Paths and cycles, See also {90B10}

05C55 Generalized Ramsey theory

05C25 Graphs and groups, See also {20F32}

Abstract: Graphs are attached to $\mathbbm{Z}_{2^r}^d$ where $\mathbbm{Z}_{2^r}$ is the ring with $2^r$
elements using an analogue of Euclidean distance. M. R. DeDeo (2003) showed
that these graphs are non-Ramanujan for $r \geqslant 4$. In this paper, we
will show that finite Euclidean graphs attached to $\mathbbm{Z}_{2^r}^d$ are non
Ramanujan for $r \geqslant 2$ except for $r=2$ and $d=2, 3$. Together with the results in Medrano
et al. (1998), this implies that finite Euclidean graphs over $\mathbbm{Z}_{p^r}$ for $p$ prime
are non-Ramanujan except for the smallest cases.