Girth of the algebraic 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$. Its exact girth $g=g(D(k,q))$ was conjectured in 1995 to be $k+5$ for odd $k$ and $q\ge 4$. This conjecture was shown to be valid in 2016 when $\frac{k+5}{2}{|}_p(q-1)$, where $p$ is the characteristic of ${\mathbb{F}}_q$ and $m{|}_{p}n$ means that $m$ divides $p^{r}n$ for some nonnegative integer $r$. In this paper, for $t\ge 1$ we prove that (a) $g(D(4t+2,q))=g(D(4t+1,q))$; (b) $g(D(4t+3,q))=4t+8$ if $g(D(2t,q))=2t+4$; (c) $g(D(8t,q))=8t+4$ if $g(D(4t-2,q))=4t+2$; (d) $g(D(2^{s+2}(2t-1)-5,q))=2^{s+2}(2t-1)$ if $p\ge 3$, $(2t-1){|}_p(q-1)$ and $2^s\Vert (q-1)$. A simple upper bound for the girth of $D(k,q)$ is proposed in the end of this paper.