1. Semicubic cages and small graphs of even girth from voltage graphsFlor Aguilar, Gabriela Araujo-Pardo, Leah Berman, 2026, original scientific article Abstract: A ({3, m}; g)-semicubic graph is a graph where the degree of each vertex is either 3 or m and the girth of the graph is g; if m = 3 we have a cubic graph. In this paper, we construct families of semicubic graphs of even girth and small order using two different techniques. The first technique generalizes a previous construction, which glues cubic cages of girth g together at remote vertices (vertices at distance at least g/2). The second technique, the main content of this paper, produces bipartite semicubic ({3, m}; g)-graphs of even girth g using voltage graphs over ℤm. For girth g = 4t + 2, t ≥ 1, the constructed graphs have two vertices of degree m. For girth g = 4t, t ≥ 2, the construction produces graphs with exactly three vertices of degree m (of course, the remaining vertices are of degree 3 in both cases). In particular, we describe infinite families of ({3, m}; g)−semicubic graphs for g = {6, 8, 10, 12} for infinitely many values of m. The cases g = {6, 8} include the unique 6-cage and the unique 8-cage when m = 3. The families obtained in this paper for girth g = {10, 12} include examples of orders that match the best-known bounds for ({3, m}; g)−semicubic graphs until this moment.
Keywords: Graph, semicubic graph, girth, voltage graph
Published in RUP: 17.08.2026; Views: 355; Downloads: 11
 Full text (574,36 KB) |
2. On (r,g,χ)- graphs and cages of regularity r, girth g and chromatic number χGabriela Araujo-Pardo, Julio César Díaz-Calderón, Julián Fresán-Figueroa, Diego González-Moreno, Linda Lesniak, Mika Olsen, 2025, original scientific article Abstract: For integers r ≥ 2, g ≥ 3 and χ ≥ 2, an (r, g, χ)-graph is an r-regular graph with girth g and chromatic number χ. Such a graph of minimum order is called an (r, g, χ)-cage. Here we prove the existence of (r, g, χ)-graphs for all r and even g when χ = 2 and for all r and g when χ = 3. Furthermore, using both existence proofs and explicit constructions we give examples of (r, g, χ)-graphs for infinitely many values of r, g, χ.
Keywords: graphs, cages, girth, chromatic number
Published in RUP: 03.11.2025; Views: 1173; Downloads: 17
Full text (408,46 KB) |
3. On extremal (almost) edge-girth-regular graphsGabriela Araujo-Pardo, György Kiss, István Porupsánszki, 2025, original scientific article Abstract: A k-regular graph of girth g is called an edge-girth-regular graph, or an egr-graph for short, if each of its edges is contained in exactly λ distinct g-cycles. An egr-graph is called extremal for the triple (k, g, λ) if has the smallest possible order. We prove that some graphs arising from incidence graphs of finite planes are extremal egr-graphs. We also prove new lower bounds on the order of egr-graphs.
Keywords: edge-girth-regular graph, cage problem, finite biaffine planes
Published in RUP: 03.11.2025; Views: 1181; Downloads: 10
Full text (547,76 KB) |
4. A note on girth-diameter cagesGabriela Araujo-Pardo, Marston D. E. Conder, Natalia García-Colín, György Kiss, Dimitri Leemans, 2025, original scientific article 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 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.
Keywords: cages, girth, degree-diameter problem
Published in RUP: 10.06.2025; Views: 1643; Downloads: 19
Full text (378,53 KB)
This document has more files! More... |
5. |
