Repository of University of Primorska

In this paper we introduce a problem closely related to the Cage Problem and the Degree Diameter Problem. For integers k ≥ 2, g ≥ 3 and d ≥ 1, we define a (k g, d)-graph to be a k-regular graph with girth g and diameter d. We denote by n₀(k g, d) the smallest possible order of such a graph, and, if such a graph exists, we call it a (k g, d)-cage. In particular, we focus on (k 5, 4)-graphs. We show that n₀(k 5, 4) ≥ k² + k + 2 for all k, and report on the determination of all (k 5, 4)-cages for k = 3, 4 and 5 and of examples with k = 6, and describe some examples of (k 5, 4)-graphs which prove that n₀(k 5, 4) ≤ 2k² for infinitely many k

Araujo-Pardo, Gabriela

Conder, Marston D. E.

García-Colín, Natalia

Kiss, György

Leemans, Dimitri

ISSN 2590-9770
The Art of Discrete and Applied Mathematics 8 (2025) #P3.06
https://doi.org/10.26493/2590-9770.1743.19f
(Also available at http://adam-journal.eu)
A note on girth-diameter cages*
Gabriela Araujo-Pardo†
Instituto de Matemáticas-Campus Juriquilla,
Universidad Nacional Autónoma de México, México.
Marston Conder‡
Department of Mathematics, University of Auckland, New Zealand
Natalia García-Colín
Département d’Informatique, Université Libre de Bruxelles, Belgium and
Department of Statistical Learning, ScaDS.AI Leipzig, Germany
György Kiss§
Department of Geometry and HUN-REN-ELTE Geometric and Algebraic Combinatorics,
Research Group, Eötvös Loránd University, Hungary, and
Faculty of Mathematics, Natural Sciences and Information Technologies,
University of Primorska, Slovenia
Dimitri Leemans¶
Département de Mathématique, Université libre de Bruxelles, Belgium and
Department of Statistical Learning, ScaDS.AI Leipzig, Germany
Received 15 December 2023, accepted 21 July 2024, published online 9 June 2025
Abstract
In this paper we introduce a problem closely related to the Cage Problem and the Degree
Diameter Problem. For integers k ≥ 2, g ≥ 3 and d ≥ 1, we define a (k; g, d)-graph to be a
*This research was initiated at the BIRS workshop 23w5125 ‘Extremal Graphs arising from Designs and
Configurations’. The authors are very grateful to the organisers and to BIRS. The authors thank an anonymous
referee for their comments and suggestions that improved this paper.
†Gabriela Araujo-Pardo acknowledges support by PAPIIT-México under grant IN113324, CONAHCyT: CBF
2023-2024-552.
‡Marston Conder acknowledges support from New Zealand’s Marsden Fund (project UOA2030).
§György Kiss acknowledges support from the Hungarian National Research, Development and Innovation
Office OTKA grant no. SNN 132625.
¶Corresponding author. Dimitri Leemans acknowledges support from an Action de Recherche Concertée grant
from the Communauté Française – Wallonie Bruxelles and the Fonds National de la Recherche Scientifique de
Belgique.
cb This work is licensed under https://creativecommons.org/licenses/by/4.0/
2 Art Discrete Appl. Math. 8 (2025) #P3.06
k-regular graph with girth g and diameter d. We denote by n0(k; g, d) the smallest possible
order of such a graph, and, if such a graph exists, we call it a (k; g, d)-cage. In particular,
we focus on (k; 5, 4)-graphs. We show that n0(k; 5, 4) ≥ k2 + k + 2 for all k, and report
on the determination of all (k; 5, 4)-cages for k = 3, 4 and 5 and of examples with k = 6,
and describe some examples of (k; 5, 4)-graphs which prove that n0(k; 5, 4) ≤ 2k2 for
infinitely many k.
Keywords: Cages, girth, degree-diameter problem.
Math. Subj. Class.: 05C35, 05E30, 05B30
1 Introduction
The order of a graph is the number of its vertices, its diameter is the maximum distance
between a pair of its vertices, and its girth is the length of its smallest circuit. A graph is
k-regular if each of its vertices has exactly k neighbours.
The well-known Cage Problem involves finding the k-regular graphs of girth g with
smallest possible order n(k, g), for a given pair (k, g) of integers with k ≥ 2 and g ≥ 3.
A regular graph with these properties is called a (k, g)-cage, or simply a cage. Cages were
introduced by Tutte [16] in 1947, and the Cage Problem has been widely studied from the
time when Erdös and Sachs [11] proved their existence in 1963. A complete survey about
this topic and its relevance can be found in [12].
The equally well known Degree-Diameter Problem involves finding the k-regular graphs
of diameter d with largest possible order, for a given pair (k, d) of integers with k ≥ 2 and
d ≥ 1. In this case what is known as the ‘Moore bound’ states that the largest order is at
most 1+k+k(k−1)+ · · ·+k(k−1)d−1. It is easy to see that graphs attaining this upper
bound are cages with odd girth g = 2d+1. Conversely, if g is odd then this is also a lower
bound for the order of a k-regular graph with girth g, when d = (g − 1)/2. For a complete
review of the Degree-Diameter problem, we refer the reader to [15].
Motivated by the above background, in this paper we describe a variation of the Cage
Problem by considering a lower bound for the order of regular graphs with given girth and
given diameter, which we call girth-diameter cages (or simply gd-cages).
Specifically, for given integers k, g and d with k ≥ 2, g ≥ 3 and d ≥ 1, we define
a (k; g, d)-graph to be a k-regular graph with girth g and diameter d, and we denote by
n0(k; g, d) the smallest possible order of such a graph (if one exists). A necessary condition
for existence is ⌊ g2⌋ ≤ d (since g ≤ 2d+1), but our main interest in such graphs is in cases
where ⌊ g2⌋ ≤ d ≤ g.
In this note, we investigate what happens for the first pair of parameters that we con-
sidered interesting, namely those with girth g = 5 and diameter d = 4. In other words, we
study (k; 5, 4)-graphs.
For any (k; 5, 4)-graph G of order n, let x and y be two vertices at distance 4 from
each other. Then the neighbourhoods N(x) and N(y) of x and y must each consist of
k vertices, with N(x) ∩ N(y) = ∅, and the remaining n − 2k − 2 vertices of G form a
set M that includes all neighbours of vertices in N(x) apart from x and all neighbours
E-mail addresses: garaujo@im.unam.mx (Gabriela Araujo-Pardo), m.conder@auckland.ac.nz (Marston
Conder), natalia.garcia.colin@ulb.be (Natalia García-Colín), gyorgy.kiss@ttk.elte.hu (György Kiss),
leemans.dimitri@ulb.be (Dimitri Leemans)
G. Araujo-Pardo et al.: A note on girth-diameter cages 3
of vertices in N(y) apart from y. Hence |M | ≥ k(k − 1), and it follows that |V (G)| ≥
2 + 2k + k(k − 1) = k2 + k + 2. This number k2 + k + 2 is a Moore-like bound for
n0(k; 5, 4), which we denote by M(k; 5, 4).
Note that it is easy to obtain a generic bound for any given integers k, g and d with
k ≥ 2, g ≥ 5 and d ≥ 4.
2 (k; 5, 4)-cages for k = 3, 4, 5 and 6
For degree k = 3, we found an example of a (3; 5, 4)-graph attaining the lower bound
M(3; 5, 4) = 32 + 3 + 2 = 14, and by an easy computational search we found that up
to isomorphism there is just one other. These two (3; 5, 4)-cages are depicted in Figure 1,
with the 19 black edges in common. One of them contains the two red edges (and its
automorphism group has order 12), while the other one contains the two green edges (and
its automorphism group has order 4). These two graphs can also be found in House of
Graphs [10], with identification numbers 1000 and 50487.
Figure 1: The two graphs with degree 3, diameter 4 and girth 5.
Similarly for degree k = 4, we found that there are exactly four non-isomorphic graphs
attaining the bound M(4; 5, 4) = 42+4+2 = 22, with automorphism groups of orders 1,
2, 4 and 8. These four graphs can be found in House of Graphs, with identification numbers
50459, 49991, 49992 and 49993 respectively.
For degree k = 5, we found using a more advanced computational search that there are
exactly seven non-isomorphic graphs that attain the bound M(5; 5, 4) = 52 + 5+ 2 = 32,
with automorphism groups of orders 4, 4, 10, 10, 48, 64 and 1920. Two of the latter
seven (5; 5, 4)-cages appeared already (in a different context) in [7], namely those with
automorphism groups of orders 48 and 1920.
A similar computational search has so far also produced two non-isomorphic 6-valent
graphs that attain the bound M(6; 5, 4) = 62 + 6 + 2 = 44, with automorphism groups of
orders 40 and 240.
4 Art Discrete Appl. Math. 8 (2025) #P3.06
3 (k; 5, 4)-graphs from the Levi graphs of biaffine planes.
Some small (k; 5, 4)-graphs graphs can be obtained using an amalgamation method on the
Levi graphs (incidence graphs) of biaffine planes, as we explain below.
Definition 3.1. Let Πq be a finite projective plane of order q. A biaffine plane is obtained
from Πq by choosing a point-line pair (P, ℓ), deleting P , deleting ℓ, all the lines incident
with P and all the points belonging to ℓ. If the point-line pair is incident in Πq , then we
say that the biaffine plane is of type 1, and otherwise we say it is of type 2.
The Levi graph of Πq is a (q + 1, 6)-cage when q ≥ 2 and its diameter is 3. When
q > 2, the Levi graphs of biaffine planes are (q; 6, 4)-graphs of orders 2q2 and 2(q2 − 1),
respectively. Two vertices are at distance 4 if and only if both of them correspond either to
points on a deleted line or to lines in the same parallel class.
The first time that this type of construction was used to find graphs of girth 5 (as far
as the authors are aware), is in a paper [8] by Brown, who proved that if q ≥ 5 is a prime
power, then n(q + 2, 5) ≤ 2q2.
More sophisticated but similar construction methods have been presented by Funk [14],
Abreu et al [4], and Abajo and her co-authors in a series of papers [1, 2, 3]. In order to
construct these graphs, the authors of these papers applied the so-called ‘amalgamation’
technique. By inserting some new edges between vertices in the incidence graph of the
biaffine plane that correspond either to two points of a deleted line or to two lines of a
parallel class, they obtained regular graphs with degree q + a for certain values of a ≥ 2,
and with diameter 4 when the diameter of the amalgamated subgraph is at least 4. For
example, this happens with a q-cycle in the incidence graph of a biaffine plane of order q,
for q ≥ 7.
The exact orders of these (k; 5, 4)-graphs are a little smaller than 2k2, but generally
larger than M(k; 5, 4) = k2 + k + 2.
As mentioned before, Araujo-Pardo and Leemans [7] used a biaffine plane of type 1
to construct a (q + 1, 5, 4)-graph of order 2q2 for q = 4, and this particular graph attains
the lower bound M(5; 5, 4) = 32. Then recently Araujo-Pardo, Kiss and Porupsánszki
[6] generalised the latter graph for any 2-power q = 2r, and presented a simple geometric
construction for (q+2; 5, 4)-graphs whose order is 2q2−2, using a biaffine plane of type 2.
4 The ‘middle’ graph
For construction of the various examples we found for degree k = 5 and 6, we strongly
utilised properties of the subgraph H induced by the ‘middle’ vertex set M = V (G) \
({x} ∪ {y} ∪ N(x) ∪ N(y)) described earlier, when G is a graph attaining the bound
M(k; 5, 4). In particular:
(a) H has order k(k − 1);
(b) H is regular with degree k − 2;
(c) H has girth at least 5, so contains no circuits of length 3 or 4;
(d) H has diameter at least 3; and
(e) the vertex-set of H can be labelled with ordered pairs (i, j) with i ̸= j ∈ Zk, such
that if (i, j) is adjacent to (i′, j′) then i ̸= i′ and j ̸= j′, and two vertices (i, j) and
(i′, j′) with i = i′ or j = j′ must lie at distance at least 3, in H , from each other.
G. Araujo-Pardo et al.: A note on girth-diameter cages 5
The first three properties above are obvious. To verify the last two, let us introduce
some extra notation. Denote the k vertices in N(x) as x0, . . . xk−1, and those in N(y) as
y0, . . . yk−1, and for 0 ≤ i ≤ k − 1 define Xi = N(xi) \ {x} and Yi = N(yi) \ {y}.
Because H contains no 3-cycles, we find that Xi ∩Xj = ∅ and Yi ∩ Yj = ∅ whenever
i ̸= j, and because H contains no 4-cycles, also |Xi ∩ Yi| ≤ 1 for all i, j. Hence we can
think of each Xi as a horizontal line and each Yj as a vertical line of the k × k integer
grid corresponding to Zk × Zk with its diagonal {(j, j) : j ∈ Zk} removed, and label the
vertices of H as the pairs (i, j) with i, j ∈ Zk such that i ̸= j.
Next, there must be at least one pair of vertices in H at distance at least 3 from each
other, for otherwise a path of length 2 between vertices (i, j) and (i′, j) in H would form
a 4-cycle in G when taken together with the edges from yj to (i, j) and (i′, j). This line
of argument also implies that two vertices that share the first or the second coordinate must
lie at distance at least 3 from each other.
The examples we found (and described earlier in Section 2) have the following proper-
ties:
• When k = 3 the subgraph H of order 6 consists of three non-incident edges;
• When k = 4 the subgraph H is a 2-regular graph of order 12, and indeed in all four
examples, it is a single cycle, with girth 12 and diameter 6;
• When k = 5 the subgraph H is a 3-regular graph of order 20, with diameter 4 and
girth 5 in two cases, diameter 5 and girth 5 in three cases, and diameter 4 and girth 6
in the other two cases.
We now present the following:
Proposition 4.1. A graph H with the properties (a) to (e) listed above can be extended to
a (k; 5, 4)-cage.
Proof. Suppose that H is a graph satisfying the conditions (a) to (e). Then the set of
vertices and edges of a new graph G can be constructed by adding the 2 + 2k vertices
x, x0, . . . xk−1, y, y0, . . . , xk−1 and the edges {x, xi}, {xi, (i, j)}, {y, yj}, {yj , (i, j)} for
i, j ∈ Zk, and we immediately find that G is a k-regular graph with k(k + 1) + 2 vertices.
All that remains is to check that the diameter of G is 4 and its girth is 5.
First it is clear that every xi and every yj lies at distance at most 3 from each of x and
y, and every vertex (i, j) lies at distance 2 from each of x and y, and hence at distance at
most 3 from every xi′ and every yj′ , and at distance at most 4 from every other middle
vertex (i′, j′). It now follows easily that every two vertices lie at distance at most 4 from
each other, so the diameter is 4.
Finally, suppose that some circuit of length 3 or 4 occurs in G. Then since the girth of
H is at least 5, at least one of the vertices of that circuit lies in H and at least one lies in
G − H . The latter vertex cannot be x or y, so that circuit must contain some xi or some
yj , but neither of x and y. Hence the circuit contains two vertices (i, j) and (i′, j′) with
i = i′ or j = j′, but then by property (e) those two vertices lie at distance at least 3 from
each other in H , so the circuit must contain another vertex of G−H either adjacent to both
(i, j) and (i, j′), or adjacent to both (i, j) and (i′, j), which is impossible. Hence the girth
of G is 5.
6 Art Discrete Appl. Math. 8 (2025) #P3.06
5 Future work
Using the above Proposition, the search for (k; 5, 4)-cages may be reduced to the search for
suitable ‘middle’ graphs satisfying the conditions (a) to (e) given in the previous section.
Some of us are continuing to search for possible constructions of such graphs that would
work for other values of the degree k ≥ 6.
We also make two key observations, namely that (1) the middle graph H is a (k−2, g)-
graph, where g ≥ 5, and has order
k(k − 1) = (k − 2)2 + 3(k − 2) + 2 = M(k − 2; 5, 4) + 2(k − 2),
and that (2) for k ≥ 14 the order of the record holder (k − 2, 5)-graphs is greater than this
number (see [12] and Table 1 in [2]). Hence it would seem to be quite a challenge to find
(k; 5, 4)-cages with order k2 + k + 2 for large k.
Clearly there are many possible directions or questions that we could proceed to con-
sider, such as the following:
• Finding bounds and examples for other values of diameter and girth.
• Restriction to Cayley or vertex-transitive graphs, or other classes of graphs with pre-
scribed symmetry.
• Construction of asymptotically ‘good’ graphs when the bound cannot be attained.
• Undertaking the same study in the context of biregular graphs [9], bipartite biregular
graphs [13], or mixed graphs [5], for instance. (There are some published papers
on such graphs related with this topic, but our reference list includes only relevant
introductory papers.)
• Finally, we make the point that in this note we consider only one of the directions
in which the degree diameter and girth problems could be extended; obviously an-
other natural direction would be to ask about the largest [k; d, g]-graph that can be
constructed with ⌊ g2⌋ ≤ d, and call that a dg-Moore graph.
ORCID iDs
Gabriela Araujo-Pardo https://orcid.org/0000-0003-3804-1855
Marston Conder https://orcid.org/0000-0002-0256-6978
Natalia García-Colín https://orcid.org/0009-0005-9106-1574
György Kiss https://orcid.org/0000-0003-3312-9575
Dimitri Leemans https://orcid.org/0000-0002-4439-502X
References
[1] E. Abajo, G. Araujo-Pardo, C. Balbuena and M. Bendala, New small regular graphs of girth
5, Discrete Math. 340 (2017), 1878–1888, doi:10.1016/j.disc.2017.03.020, https://doi.
org/10.1016/j.disc.2017.03.020.
[2] E. Abajo, C. Balbuena, M. Bendala and X. Marcote, Improving bounds on the order of regu-
lar graphs of girth 5, Discrete Math. 342 (2019), 2900–2910, doi:10.1016/j.disc.2019.02.007,
https://doi.org/10.1016/j.disc.2019.02.007.
G. Araujo-Pardo et al.: A note on girth-diameter cages 7
[3] E. Abajo and M. Bendala, Regular graphs of girth 5 from elliptic semiplanes of type C, Discrete
Math. 344 (2021), 9, doi:10.1016/j.disc.2021.112343, id/No 112343, https://doi.org/
10.1016/j.disc.2021.112343.
[4] M. Abreu, G. Araujo-Pardo, C. Balbuena and D. Labbate, Families of small regular graphs
of girth 5, Discrete Math. 312 (2012), 2832–2842, doi:10.1016/j.disc.2012.05.020, https:
//doi.org/10.1016/j.disc.2012.05.020.
[5] G. Araujo-Pardo, C. Hernández-Cruz and J. J. Montellano-Ballesteros, Mixed cages, Graphs
Comb. 35 (2019), 989–999, doi:10.1007/s00373-019-02050-1, https://doi.org/10.
1007/s00373-019-02050-1.
[6] G. Araujo-Pardo, Gy. Kiss and I. Porupsánszki, On extremal (almost) edge-girth-regular
graphs, Art. Discrete Appl. Math. 8 (2025), Id/No P3.05, 21 pp., doi:10.26493/2590-9770.
1733.dc9, https://doi.org/10.26493/2590-9770.1733.dc9.
[7] G. Araujo-Pardo and D. Leemans, Edge-girth-regular graphs arising from biaffine planes and
Suzuki groups, Discrete Math. 345 (2022), 10, doi:10.1016/j.disc.2022.112991, Id/No 112991,
https://doi.org/10.1016/j.disc.2022.112991.
[8] W. G. Brown, On the non-existence of a type of regular graphs of girth 5, Can.
J. Math. 19 (1967), 644–648, doi:10.4153/CJM-1967-058-3, https://doi.org/10.
4153/CJM-1967-058-3.
[9] G. Chartrand, R. J. Gould and S. F. Kapoor, Graphs with prescribed degree sets and girth,
Period. Math. Hung. 12 (1981), 261–266, doi:10.1007/BF01849614, https://doi.org/
10.1007/BF01849614.
[10] K. Coolsaet, S. D’hondt and J. Goedgebeur, House of graphs 2.0: a database of interesting
graphs and more, Discrete Appl. Math. 325 (2023), 97–107, doi:10.1016/j.dam.2022.10.013,
https://doi.org/10.1016/j.dam.2022.10.013.
[11] P. Erdős and H. Sachs, Reguläre graphen gegebener taillenweite mit minimaler knotenzahl,
Wiss. Z. Uni. Halle (Math. Nat.) 12 (1963), 251–258.
[12] G. Exoo and R. Jajcay, Dynamic cage survey, Electron. J. Comb. DS16 (2008), 48, doi:10.
37236/37, https://doi.org/10.37236/37.
[13] S. Filipovski, A. R. Rivera and R. Jajcay, On biregular bipartite graphs of small excess, Discrete
Math. 342 (2019), 2066–2076, doi:10.1016/j.disc.2019.04.004, https://doi.org/10.
1016/j.disc.2019.04.004.
[14] M. Funk, Girth 5 graphs from elliptic semiplanes, Note Mat. 29 (2009), 93–
117, doi:10.1285/i15900932v29n1supplp91, https://doi.org/10.1285/
i15900932v29n1supplp91.
[15] M. Miller and J. Širáň, Moore graphs and beyond: a survey of the degree/diameter prob-
lem, Electron. J. Comb. DS14 (2013), 61 pp., doi:10.37236/35, https://doi.org/10.
37236/35.
[16] W. T. Tutte, A family of cubical graphs, Proc. Camb. Philos. Soc. 43 (1947), 459–474.


English

A note on girth-diameter cages

Mohar, Maja

Krajnčan, Mitja

Slovene

Učinkovitost uporabe terapij s konji na osebe s posebnimi potrebami

Volk, Luka

Volmut, Tadeja

Gibalna/športna aktivnost, gibalne sposobnosti in telesna samopodoba pri osnovnošolcih

Vrtovec, Leon

Kavrečič Božeglav, Petra

Oblikovanje kraja kolektivnega spomina na primeru postavitve spomenika Nazariu Sauru v Kopru

Beravs, Polonca

Bertoncel, Tine

Digitalna transformacija

Bukovec, Nika

Furlan, Petra

Prehrana predšolskih otrok in spodbujanje zdravih prehranjevalnih navad v vrtcu

Grmek, Maja

Kozinc, Žiga

Povezava med jakostjo mišic iztegovalk, odmikalk in zunanjih rotatorjev kolka in valgusom kolena pri treh gibalnih testih

University of Primorska

Not a member yet

A note on girth-diameter cages

Učinkovitost uporabe terapij s konji na osebe s posebnimi potrebami

Gibalna/športna aktivnost, gibalne sposobnosti in telesna samopodoba pri osnovnošolcih

Oblikovanje kraja kolektivnega spomina na primeru postavitve spomenika Nazariu Sauru v Kopru

Digitalna transformacija

Prehrana predšolskih otrok in spodbujanje zdravih prehranjevalnih navad v vrtcu

Povezava med jakostjo mišic iztegovalk, odmikalk in zunanjih rotatorjev kolka in valgusom kolena pri treh gibalnih testih

Government support to entrepreneurship

Pouk matematike na prostem v 4. razredu osnovne šole

Uspešno sodelovanje zaposlenih v timu zdravstvene nege

15,971

20,883