On balanced biregular cages
Gabriela [email protected], György [email protected] · 2026
Read On balanced biregular cages by Gabriela [email protected], György [email protected] (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2604-22395.txt.
Introduction
From incidence graphs of finite biaffine, affine, and projective planes, Araujo-Pardo and Kiss build relatively small balanced biregular graphs. Some of the graphs they obtain are balanced biregular cages. A balanced biregular cage is the smallest biregular graph of fixed girth with equal numbers of vertices of each degree. For some degree and girth values the pair also pins down lower and upper bounds. The work belongs to a problem closely tied to the cage problem.
Catalog record
| CREATOR | Gabriela [email protected], György [email protected] |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 52731 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2604.22395
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
On balanced biregular cages Gabriela [email protected], György [email protected] Abstract In this paper, we introduce a problem closely related to the Cage Problem . We are interested in Balanced Biregular Cages , which are the smallest biregular graphs of fixed girth that have the same number of vertices of one degree as the other. We introduce the graphs and obtain lower and upper bounds for some values of degree and girth. In particular, we construct relatively small balanced biregular graphs from incidence graphs of finite projective, affine, and biaffine planes and we show that some of the obtained graphs are balanced biregular cages. 1 1 footnotetext: Research supported in part by PAPIIT-UNAM-México IN113324, and SECIHTI-México under Project CBF2023-2024-552. 2 2 footnotetext: This research was supported in part by the Hungarian National Research, Development and Innovation Fund, grant numbers ADVANCED 153080 and SNN 152582, and by the Slovenian Research Agency, research program N1-0429. MSC: 05C035, 51E20 Keywords: cage problem, biregular graphs, finite planes 1 Introduction Many issues in extremal graph theory involve finding the maximum or minimum of a graph parameter subject to constraints on other parameters or structural properties. Often, these studies focus on estimating key quantities such as the number of vertices or edges. In this paper, we explore similar questions, which are also inspired by the classic Cage Problem , which consists of finding regular graphs of fixed girth (length of the smallest cycle) and minimum order. There exist a lot of different generalizations of this problem, one of them asks about graphs with a given degree set, a fixed girth, and minimum order. These graphs were introduced by Chartrand, Gould, and Kapoor in [ 16 ] , and also in that paper, they focus on the question of biregular graphs (where the degree set has exactly two elements). Also, Yuansheng and Liang [ 32 ] studied these biregular graphs and gave interesting lower and upper bounds for some specific girths, one of which is the lower bound for biregular graphs of girth 6 . After that, many authors have studied bipartite cages and obtained different results regarding their order, see [ 8 , 13 , 21 , 22 , 27 ] . Later, Filipovski, Jajcay, and Ramos-Rivera [ 23 ] further specialized the problem for bipartite biregular graphs, that is, for bipartite graphs with the property that the vertices of one bipartition set have degree m and the vertices of the other bipartition set have degree n . Note that, since the graphs are bipartite, the girth is even. We would like to emphasize that one of the differences between the problems of finding biregular and bipartite biregular cages is related to the "balance" between the vertices of one degree and the other. While, in the problem of finding biregular cages, it is essential to have only a small number of vertices of higher degree, in the case of bipartite biregular graphs it is crucial to consider arithmetic relationships between the two degree values that allow one side of the partition to consist of vertices of one degree and the other side of vertices of the other degree. In this paper, we introduce a third variation of the biregular cage problem, which we refer to as the balanced problem. We ask about the existence of balanced bipartite cages , defined as biregular graphs with a fixed girth and minimum order, in which the number of vertices of one degree is equal to the number of vertices of the other. We start the paper recalling the traditional Cage Problem: A simple, finite, connected graph G=(V,E) is k -regular if each vertex has exactly k neighbors. It is of girth g if its smallest cycles have g vertices. A g -cycle or girth cycle is a cycle of length g . The number of vertices of G is called the order of G . A (k,g) -graph is a k -regular graph of girth g . If it has minimal order, then it is called a (k,g) -cage . For more information about cages, we refer to the dynamic survey by Exoo and Jajcay [ 20 ] . For k=2 the connected (k,g) -graphs are the g -cycles. For k>2 , the well-known Moore bound is obtained by counting the vertices of a tree that emerge from a vertex if the girth is odd, or from an edge if g is even. As we will use these trees, called Moore trees , and their modifications on several occasions throughout this work, we provide a brief description of them. Let u be a vertex and let {\cal{T}}_{u} be a tree of depth \frac{g-1}{2} , rooted in u , with all the vertices of degree k except the leaves. Notice that, if G is a k -regular graph of odd girth g , then G necessarily contains this tree, denoted by {\cal{T}}_{u} . On the other hand, if g is even and uw is an edge, then a Moore tree for even girth, denoted by {\cal{T}}_{uw} , consist of the edge uw and two disjoint trees, {\cal{T}}_{u} and {\cal{T}}_{w} rooted in u and w , respectively. Both {\cal{T}}_{u} and {\cal{T}}_{w} have depth \frac{g-2}{2} and all the vertices have degree k , except the leaves. As before, if G is a k -regular graph of even girth g , then G must contain {\cal{T}}_{uw} . Counting the vertices of these Moore trees results in the following bound. Theorem 1.1 (Moore bound, [ 20 ] ) . Let G be a (k,g) -graph with k>2 . Then the order of G is at least n_{0}(k,g) , where n_{0}(k,g)=\begin{cases}\frac{k(k-1)^{\frac{g-1}{2}}-2}{k-2},\quad\text{if g is odd;}\\ \frac{2(k-1)^{\frac{g}{2}}-2}{k-2},\quad\text{~~if g is even.}\end{cases} In this paper, we will study the balanced bipartite cages , shorter the babi-cages , defined as follows: Definition 1.2 . Let 1\leq r\leq s and 3\leq g be integers. An (r,s;g) -balanced biregular graph is a graph of girth g having degree set equal to \{r,s\} and satisfying the additional property that the number of vertices of degree r equals the number of vertices of degree s . We denote it as (r,s;g) -babi-graph and call it, for short, a babi-graph. An (r,s;g) - balanced biregular cage (for short an (r,s;g) -babi-cage) is an (r,s;g) -babi-graph of minimum order. Moreover, n_{bb}(r,s;g) denotes the order of an (r,s;g) -babi-cage. In the first part of the paper (Sections 2 and 3), we introduce some basic concepts related to babi-graphs. Using the corresponding Moore trees, we give a general lower bound on the size of babi-graphs and present the babi-cages for g=3 and 4 . In the second part of the paper (Chapters 4 and 5), we consider constructions of babi-graphs with girth 5 and 6 mostly from incidence graphs of projective and biaffine planes. Our motivation comes from the fact that the incidence graphs of projective planes are known to be extremal with regard to the girth 6 . An introduction to finite geometries and the detailed description of concepts we use can be found, for example, in [ 29 ] . Here we give only the most necessary definitions. A finite projective plane of order q has q^{2}+q+1 points and q^{2}+q+1 lines, and it satisfies the following four axioms: