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

Rights

URN

URN:NBN:SI:DOC-1SK2M1ZU

COBISSID

238839043

DOI

10.26493/2590-9770.1743.19f

Added

20.02.2026

Metadata

Citation

APA:

Araujo-Pardo, Gabriela, Conder, Marston D. E., García-Colín, Natalia, Kiss, György, Leemans, Dimitri (2025). A note on girth-diameter cages. The art of discrete and applied mathematics, volume 8, issue 3, article p3.06, str. 1-7. URN:NBN:SI:DOC-1SK2M1ZU from http://www.dlib.si

MLA:

Araujo-Pardo, Gabriela, Conder, Marston D. E., García-Colín, Natalia, Kiss, György, Leemans, Dimitri. "A note on girth-diameter cages." The art of discrete and applied mathematics volume 8. issue 3. article p3.06 (2025) str. 1-7.
<http://www.dlib.si/?URN=URN:NBN:SI:DOC-1SK2M1ZU>