Araujo-Pardo–Leemans family conjecture for edge-girth-regular graphs

Let egr(v,k,g,λ)egr(v,k,g,\lambda) denote an edge-girth-regular graph with vv vertices, valency kk, girth gg, and each edge contained in exactly λ\lambda cycles of length gg. Let q3q\geq 3 be a prime power and let g{8,12}g\in\{8,12\}. Araujo-Pardo–Leemans conjecture. There exists a family of

egr(2qg22,q,g,(q1)g22(q2))egr\left(2q^{\frac{g-2}{2}},q,g,(q-1)^{\frac{g-2}{2}}(q-2)\right)

graphs, and these graphs are extremal edge-girth-regular graphs, meaning that they attain the minimum possible order for their parameters. The conjecture proposes infinite families in the cases g=8g=8 and g=12g=12. The paper states that its computations disprove the conjecture for cubic graphs of girths 88 and 1212, so the conjecture is refuted as stated.

Sources & referencesView supporting material

Primary source

Jan Goedgebeur and Jorik Jooken, “Exhaustive generation of edge-girth-regular graphs”, arXiv:2401.08271 (2024).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.