Does there exists a growing sequence of simple connected regular graphs of girth $k$ ($k \geq 5$) with uniformly bounded diameter?

Question

Fix any $k \geq 5$.

Does there exist a growing sequence of simple connected REGULAR graphs, each of girth $k$, where the number of vertices $n$ goes to infinity and where the diameter of each graph is uniformly bounded in $n$?

Answer 1

Sure: You can use generalized polygons. For instance, take incidence graphs ${\mathcal G}_q$ of the finite projective planes $P(q)$ of the finite fields $F_q$ of order $q$ (say, $q$ is prime, then the field is ${\mathbb Z}/q{\mathbb Z}$). Such incidence graph is the bipartite graph whose vertices are lines and planes in the 3-dimensional vector space $V=F_q^3$. Two vertices are connected by an edge precisely when the line is contained in the plane. Every such graph has valence $q+1$, diameter 3 and girth 6. The graphs ${\mathcal G}_q$ have many interesting properties, for instance, their symmetry group acts transitively on ${\mathcal G}_q$: The finite linear group $GL(3, F_q)$ acts transitively on the sets of lines and of planes but one can also switch lines and planes.

Let's prove that each ${\mathcal G}_q$ has diameter 3: One can think of this as an exercise either in linear algebra or in projective geometry. Via linear algebra: If, say, $P_1, P_2$ are distinct planes in $V$, their intersection in $V$ is a line, hence, the graph-distance $d(P_1,P_2)$ from $P_1$ to $P_2$ is 2. Similarly, if $L_1, L_2$ are distinct lines in $V$, their span is a plane, hence, again, $d(L_1, L_2)=2$. Lastly, if $P$ is a plane and $L$ is a line not in that plane, take a line $L'\subset P$. Then $d(P,L')=1, d(L,L')=2$, thus, $d(P,L)=3$ (it cannot be less than $3$).

Let's prove that girth is 6: Take three coordinate planes and three coordinate lines in $V=F_q^3$. Together, they form a cycle of length 6 in the incidence graph. (Geometrically, you draw a triangle in the projective plane and consider its set of edges and vertices, you get a hexagon which is the cycle of length 6 I just described.)

It is another linear algebra/projective geometry exercise to prove that ${\mathcal G}_q$ contains no cycles of length 4. (For any two distinct points in a projective plane there is exactly one projective line through these points.)

Edit. Similarly to Alex's answer, generalized polygons (of arbitrarily high but finite cardinality) and of fixed girth $g\ge 5$ (and diameter $d=g/2$) exist only for small values of the diameter: $d=3, 4, 6, 8$.

Answer 2

$\newcommand{\diam}{\operatorname{diam}}$ The answer is positive for girth $g\in \{5,6,7,8,12\}$.

To show that the graphs from the references are examples, we use the following arguments.

Below $d\ge 2$, $g\ge 3$ are natural numbers, and $G$ is a $d$-regular graph $G$ of girth $g$, order $n$, and diameter $\diam G$. Put $g’=\lfloor (g-1)/2\rfloor$. Let $v$ be any vertex $v$ of $G$ let $B(u)$ be the set of vertices $u$ of $G$ such that the distance from $v$ to $u$ is at most $g’$. $$|B(u)|=1+d+d(d-1)+\dots +d(d-1)^{g’-1}=1+\frac {d(d^{g’}-1)}{d-1}.$$ Denote the latter value by $b(d,g)$.

Lemma. $\left\lfloor 1+\frac{\diam G}{2g’+1}\right\rfloor b(d,g)\le n$.

Proof. Let $m=\diam G$. Pick vertices $v_0$ and $v_m$ of the graph such that the distance between them equals $m$ and let $v_0-v_1-\dots-v_m$ be a shortest path from $v_0$ to $v_m$. Then sets $B(v_0), B(v_{2g’+1}), B(v_{4g’+2}), \dots$ are mutually disjoint, otherwise we can make a shortcut in the path. It follows the lemma’s claim. $\square$

A $(d, g)$-graph is a $d$-regular graph of girth $g$. Erdős and Sachs [ES] proved the existence of $(d,g)$-graphs for all $d\ge 2$ and $g\ge 3$. Let $n(d,g)$ be the minimum order of $(d, g)$-graph. Lemma follows if $n(d,g)\le 2(d,g)-1$ then there exists a $(d,g)$-graph of diameter at most $2g’\le g$.

By Theorem 16 from [EJ], when $5\le g\le 8$ and $d$ is an odd prime power then $n(d,g)\le m(d,g)$. Also I expect a lot of constructions of $d$-regular graphs of girth $g$ and order at most $2b(d,g)-1$ is listed in [EJ], Section 4.1.2 (for girth $5$) and Section 4.1.3 (for girths $6$, $8$, and $12$). For instance, Construction XX by Gács and Héger shows that $n(d,12)\le m(d,12)$, when $d$ is a prime power. See also Section 4.1.4.

In [AFLN] and [AA-PBL2] are listed results on $n(d,5)\le 2b(d,5)-1$, see also [AA-PBL2, Proposition 2]. In [AA-PBL] are presented similar results for $g=7$ (Theorems 3.1 and 3.2) and $g=8$ (Theorems 3.3, 3.4, possibly, 3.5, and the references after it). Maybe some references from Introduction of [AA-PBL2] and Section 3.5.2 of [MS] can be helpful.

References

[AFLN] M. Abreu, M. Funk M., D. Labbate, V. Napolitano,A family of regular graphs of girth 5, Discrete Mathematics 308 (2008) 1810–1815.

[AA-PBL] M. Abreu, G. Araujo-Pardo, C. Balbuena, D. Labbate, A formulation of a $(q+1,8)$-cage.

[AA-PBL2] M. Abreu, G. Araujo-Pardo, C. Balbuena, D. Labbate, Families of small regular graphs of girth 5, Discrete Mathematics 312 (2012) 2832–2842.

[EJ] Geoffrey Exoo, Robert Jajcay, Dynamic Cage Survey, The electronic jornal of combinatorics, dynamic survey 16.

[ES] P. Erdős, H. Sachs, Reguläre Graphen gegebener Taillenweite mit minimaler Knotenzahl, Wiss. Z. Uni. Halle (Math. Nat.), 12 (1963) 251–257.

[MS] Mirka Miller, Jozef Širáň, Moore graphs and beyond: A survey of the degree/diameter problem, The electronic jornal of combinatorics 20:2, dynamic survey 14v2.