On the algebraic bipartite graphs $D(4s,q)$

Lazebnik-Ustimenko graphs $D(k,q)$ constitute a notable family of $q$-regular, edge-transitive bipartite graphs characterized by high symmetry and large girth, with wide applications in algebraic graph theory and coding theory. The precise girth of $D(k,q)$ is governed by a celebrated conjecture proposed by Füredi et al., which remains unresolved in general cases. Although prior works have validated this conjecture for several specific parameter regimes and established fundamental structural properties of graph girth, a systematic characterization of girth cycles for even-indexed subfamilies of \(D(k,q)\) is still absent. This paper focuses on the graph subclass $D(4s,q)$ and conducts structural analysis via its isomorphic bipartite model $Λ_{k,q}$. We derive an explicit necessary and sufficient condition for the existence of length-$(4s+4)$ backtrackless circuits in $Λ_{4s,q}$. Using this criterion, we completely characterize all girth cycles of $Λ_{8,q}$ and verify the Füredi-Lazebnik-Ustimenko girth conjecture for the parameter family $k=2(p^r+1)p^t-4$ over finite fields of odd characteristic $p\geq 3$ with $q=p^m>3$. The results further enrich the structural theory of symmetric large-girth bipartite graphs and extend the valid parameter range of this classic girth conjecture.

Authors

Publication Details

Journal
arXiv (Cornell University)
Published
2026-11-12
DOI
https://doi.org/10.48550/arxiv.2611.16470
Primary Topic
Limits and Structures in Graph Theory
Type
preprint
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
NOV
preprint

On the algebraic bipartite graphs $D(4s,q)$

Yuansheng Tang, Chen Zhang, Ming Xu, Xiaoyan Cheng
arXiv (Cornell University)
Limits and Structures in Graph Theory
preprint

On the algebraic bipartite graphs $D(4s,q)$

Yuansheng Tang, Chen Zhang, Ming Xu, Xiaoyan Cheng
preprint en

Abstract

Lazebnik-Ustimenko graphs $D(k,q)$ constitute a notable family of $q$-regular, edge-transitive bipartite graphs characterized by high symmetry and large girth, with wide applications in algebraic graph theory and coding theory. The precise girth of $D(k,q)$ is governed by a celebrated conjecture proposed by Füredi et al., which remains unresolved in general cases. Although prior works have validated this conjecture for several specific parameter regimes and established fundamental structural properties of graph girth, a systematic characterization of girth cycles for even-indexed subfamilies of \(D(k,q)\) is still absent. This paper focuses on the graph subclass $D(4s,q)$ and conducts structural analysis via its isomorphic bipartite model $Λ_{k,q}$. We derive an explicit necessary and sufficient condition for the existence of length-$(4s+4)$ backtrackless circuits in $Λ_{4s,q}$. Using this criterion, we completely characterize all girth cycles of $Λ_{8,q}$ and verify the Füredi-Lazebnik-Ustimenko girth conjecture for the parameter family $k=2(p^r+1)p^t-4$ over finite fields of odd characteristic $p\geq 3$ with $q=p^m>3$. The results further enrich the structural theory of symmetric large-girth bipartite graphs and extend the valid parameter range of this classic girth conjecture.

arXiv (Cornell University)
Limits and Structures in Graph Theory
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Laika access coming soon