Papers › On vertex-girth-regular graphs: (Non-)existence, bounds and enumeration
On vertex-girth-regular graphs: (Non-)existence, bounds and enumeration
Robert Jajcay, Jorik Jooken, István Porupsánszki
The archive published only this paper's code-link row. Authors, date and abstract are from arXiv's metadata (CC0), read from the Kaggle arXiv metadata snapshot of 2026-09-12 where its title matched the archive's; the title is the archive's.
A vertex-girth-regular vgr(v,k,g,λ)-graph is a k-regular graph of girth g and order v in which every vertex belongs to exactly λ cycles of length g. While all vertex-transitive graphs are necessarily vertex-girth-regular, the majority of vertex-girth-regular graphs are not vertex-transitive. Similarly, while many of the smallest k-regular graphs of girth g, the so-called (k,g)-cages, are vertex-girth-regular, infinitely many vertex-girth-regular graphs of degree k and girth g exist for many pairs k,g. Due to these connections, the study of vertex-girth-regular graphs promises insights into the relations between the classes of extremal, highly symmetric, and locally regular graphs of given degree and girth. This paper lays the foundation to such study by investigating the fundamental properties of vgr(v,k,g,λ)-graphs, specifically the relations necessarily satisfied by the parameters v,k,g and λ to admit the existence of a corresponding vertex-girth-regular graph, by presenting constructions of infinite families of vgr(v,k,g,λ)-graphs, and by establishing lower bounds on the number v of vertices in a vgr(v,k,g,λ)-graph. It also includes computational results determining the orders of smallest cubic and quartic graphs of small girths.
Code
Repository list and official/mentioned flags are the archive's, frozen 2025-07-28. Reachability, where shown, is from one Syntology probe window (2026-09-16 to 2026-09-18); repositories not probed show nothing. GitHub stars are not tracked.
Code Syntology ran Syntology
Not run by Syntology. Nothing on this page verifies that the listed code works.
Results from the paper archive 2025-07-28
No leaderboard rows for this paper in the archive.
Report a problem or propose a change · a person checks every report against the paper or source before anything changes; decisions are listed on /corrections