The bipartite graphs $D’(k,q)$ have low girth

In [Mukherjee, Eur. J. Comb. 2024], we introduced a family of $3$-uniform hypergraphs $D_3(k,q)$ extending the Lazebnik–Ustimenko–Woldar graphs $D(k,q)$. For $3\mid q$, the link graphs of $D_3(k,q)$ include a new family of bipartite graphs $D’(k,q)$. Due to computational evidence that $D’(k,q)$ and $D(k,q)$ have the same girth for $k\le 18$ and $q = 3$, it was hoped that the high-girth property persists for every $q = 3^n$. We show that this hope fails for every nontrivial extension of $\mathbb F_3$: for $q = 3^n$ with $n \ge 2$ and $k \ge 2$, the graph $D’(k,q)$ contains a cycle of length $10$. In particular, the girth of $D’(k,q)$ for $k \ge 5$ is at most $10$. The proof constructs two length-five walks from the zero vertex that share a common midpoint, using an involution of $\mathbb F_q$ and a symbolic block induction over $\mathbb F_3[X]$. The accompanying repository \texttt{https://github.com/Potla1995/dgraphs} contains the computations that motivated the construction and verify representative finite cases; the proof itself is algebraic.

Author’s preprint

Code repository

A preliminary version of this work was presented at the 57th Southeastern International Conference on Combinatorics, Graph Theory and Computing (March 2026).

Will be uploaded to arXiv soon…