On the girth cycles of the bipartite graph $D(k,q)$

Abstract

For integer $k\ge 2$ and prime power $q$, the algebraic bipartite graph $D(k,q)$ proposed by Lazebnik and Ustimenko (1995) is meaningful not only in extremal graph theory but also in coding theory and cryptography. This graph is $q$-regular, edge-transitive and of girth at least $k+4$. For its exact girth $g=g(D(k,q))$, Füredi et al. (1995) conjectured $g=k+5$ for odd $k$ and $q\ge 4$. This conjecture was shown to be valid in 2016 when $(k+5)/2$ is the product of an arbitrary factor of $q-1$ and an arbitrary power of the characteristic of ${\mathbb{F}}_q$. In this paper, we determine all the girth cycles of $D(k,q)$ for $3\le k\le 5$, $q>3$, and those for $3\le k\le 8$, $q=3$.