1. A classification of Q-polynomial distance-regular graphs with girth 6Štefko Miklavič, 2025, original scientific article Abstract: Let Γ denote a Q-polynomial distance-regular graph with diameter D and valency k≥3. In [Homotopy in Q-polynomial distance-regular graphs, Discrete Math., {\bf 223} (2000), 189–206], H. Lewis showed that the girth of Γ is at most 6. In this paper we classify graphs that attain this upper bound. We show that Γ has girth 6 if and only if it is either isomorphic to the Odd graph on a set of cardinality 2D+1, or to a generalized hexagon of order (1,k−1).
Keywords: distance-regular graphs, Q-polynomial property, girth
Published in RUP: 01.12.2025; Views: 204; Downloads: 3
 Full text (291,61 KB)
This document has more files! More... |
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: 310; Downloads: 2
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: 321; Downloads: 2
Full text (547,76 KB) |
4. Totally regular mixed graphs constructed from the CD(n,q) graphs of Lazebnik, Ustimenko and WoldarTatiana Jajcayova, Robert Jajcay, 2025, original scientific article Abstract: The CD(n,q) graphs are connected components of q-regular graphs D(n,q) introduced in 1995 by Lazebnik and Ustimenko. They constitute the best universal family of regular graphs of prime power degree with regard to the Cage Problem which calls for determining the orders of the smallest k-regular graphs of girth g. The girths of the CD(n,q) graphs are known to be at least n+4 in case of even n, and n+5 for odd n. We propose to extend the use of the CD(n,q) graphs into the area of mixed graphs by adding directions to certain edges of the C(n,q)graphs.
In the context of mixed graphs, graphs in which the number of incident non-oriented edges is the same for all vertices, and the numbers of out-going and in-going edges are also equal and the same for all vertices, are of special interest and are called totally regular mixed graphs. In view of the special properties of the original C(n,q) graphs with regard to cages, we believe that the totally regular mixed graphs we propose to study may also prove to be extremal with regard to properties sought for in the area of mixed graphs.
Keywords: cage problem, girth, degree, mixed graphs
Published in RUP: 03.11.2025; Views: 266; Downloads: 2
Full text (574,95 KB) |
5. 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: 728; Downloads: 15
Full text (378,53 KB)
This document has more files! More... |
6. |
7. A note on acyclic number of planar graphsMirko Petruševski, Riste Škrekovski, 2017, original scientific article Abstract: The acyclic number ▫$a(G)$▫ of a graph ▫$G$▫ is the maximum order of an induced forest in ▫$G$▫. The purpose of this short paper is to propose a conjecture that ▫$a(G)\geq \left( 1-\frac{3}{2g}\right)n$▫ holds for every planar graph ▫$G$▫ of girth ▫$g$▫ and order ▫$n$▫, which captures three known conjectures on the topic. In support of this conjecture, we prove a weaker result that ▫$a(G)\geq \left( 1-\frac{3}{g} \right)n$▫ holds. In addition, we give a construction showing that the constant ▫$\frac{3}{2}$▫ from the conjecture cannot be decreased.
Keywords: induced forest, acyclic number, planar graph, girth
Published in RUP: 03.01.2022; Views: 2164; Downloads: 22
Full text (227,50 KB) |
8. |
9. |
10. |
