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

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$$?

• Do the Murty graphs help? I don't know their diameter. Commented Jun 11, 2020 at 16:41
• I assume you mean Moore graph ? The problem is that there are finitely many Moore graphs. The idea here would be basically to find an explicit infinite sequence of regular graphs that are "near-Moore" with girth $k \geq 5$. Commented Jun 12, 2020 at 4:14
• I mean the graphs in Section 3 of core.ac.uk/download/pdf/82145602.pdf, and perhaps those in Section 4. Commented Jun 12, 2020 at 9:03
• This is really interesting, although the diameter is unclear. It doesn't look friendly to program either. Commented Jun 12, 2020 at 17:09
• By digging deeper, I found an example on page 2 here : arxiv.org/pdf/1501.02448.pdf (girth 8, diameter 4) Commented Jun 12, 2020 at 18:07

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$$.

• This is exactly the type of construction I need, but I'm not able to fully comprehend what $P(q)$ and $V$ even mean/represent. Most of all, I need an algorithm that can generate these graphs. Commented Jun 19, 2020 at 0:40
• @FrédéricOuimet: You do not need to know what $P(q)$ is if you do not know projective geometry. I described the graph ${\mathcal G}_q$ in terms of linear algebra over finite field. Did you ever take a linear algebra class? You probably used real numbers but it works the same way over any field. Concretely, $V=F_q^3$ is what I said, the set of triples $(x,y,z)$ of elements of the finite field. These triples are usually called vectors in linear algebra. You can add them, multiply by scalars (from the same finite field, of course). This is not at all different from ${\mathbb R}^3$. Commented Jun 19, 2020 at 2:38
• @FrédéricOuimet: I am absolutely sure that there are packages for doing linear algebra over finite fields. Commented Jun 19, 2020 at 2:41
• @FrédéricOuimet: Here is a link to some random paper found by my search engine, which computes incidence matrices of finite projective planes for sufficiently small $q$. Commented Jun 19, 2020 at 2:52
• Thanks. After rereading the 2nd paragraph, I now understand your proof visually. Commented Jun 19, 2020 at 3:24

$$\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.

• +1, nice ${}{}$ Commented Jun 18, 2020 at 14:24
• Do you know an algorithm that generates arbitrarily many of these graphs with programming? Commented Jun 19, 2020 at 2:23
• @FrédéricOuimet I didn’t think about that. Maybe some proposed constructions from [EJ] (for instance, Construction X) can be rather easily programmed. Commented Jun 19, 2020 at 2:30