pith. sign in

arxiv: 2604.22395 · v2 · submitted 2026-04-24 · 🧮 math.CO

On balanced biregular cages

Araujo-Pardo Gabriela , Kiss Gy\"orgy This is my paper

Pith reviewed 2026-05-12 01:44 UTC · model grok-4.3

classification 🧮 math.CO
keywords balanced biregular cagecage problemincidence graphprojective planeaffine planebiregular graphgirth
0
0 comments X

The pith

Some incidence graphs of finite planes are the smallest balanced biregular graphs of their girth.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

Balanced biregular cages are defined as the smallest biregular graphs with a prescribed girth that have an equal number of vertices of each of the two degrees. The paper derives lower bounds on the number of vertices for given degree pairs and girth, along with upper bounds from explicit constructions. It shows that incidence graphs of certain projective, affine, and biaffine planes meet these bounds and thus are cages for those parameters.

Core claim

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.

What carries the argument

Incidence graph of a finite plane, which provides a biregular bipartite graph with equal part sizes and controlled girth that can serve as a cage.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Other finite geometries or combinatorial designs could be examined to find additional balanced biregular cages.
  • These results connect the classical cage problem to the balanced variant by providing concrete examples where optimality is achieved.
  • Testing the constructions for larger planes or different parameters would yield more exact cage values.

Load-bearing premise

The incidence graphs from the planes have equal numbers of vertices in each part and the required girth, and nothing smaller satisfies the same conditions.

What would settle it

A biregular graph with the same degrees and girth, equal part sizes, but strictly fewer vertices than the plane incidence graph for a claimed cage parameter.

Figures

Figures reproduced from arXiv: 2604.22395 by Araujo-Pardo Gabriela, Kiss Gy\"orgy.

Figure 1
Figure 1. Figure 1: A (2, 4; 5)-babi-cage of order 14 (House of Graphs [17], no. 53705) For r = 3 there exists a (3, 5; 5)-babi-graph of order 28. It can be con￾structed by simple deletion from one of the (5, 5)-cages of order 30, the Robertson-Wegner graph (for short, RW) [31]. For the sake of completeness, we recall the geometric construction of RW. Let D be a regular dodecahedron. The vertices of D determine five cubes. Ea… view at source ↗
Figure 2
Figure 2. Figure 2: A (2, 3; 6)-babi-cage of order 12 (House of Graphs [17], no. 54321) There exist non-isomorphic (2, 3; 6)-babi cages of order 12. The graph given in the previous corollary can also be constructed in the following way: take two disjoint 6-cycles C1 = (0, 1, 2, 3, 4, 5) and C2 = (0′ , 1 ′ , 2 ′ , 3 ′ , 4 ′ , 5 ′ ), and add the edges {00′ , 22′ , 44′}. This graph has 3 fat edges and no thin edge. The (2, 3; 6)… view at source ↗
read the original abstract

In this paper, we introduce a problem closely related to the {\emph{Cage Problem}}. We are interested in {\emph{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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 2 minor

Summary. The manuscript introduces the notion of balanced biregular cages: the smallest graphs that are biregular (vertices have one of two distinct degrees) with a given girth g and with an equal number of vertices of each degree. General lower bounds on the number of vertices are derived for given degrees and girth. Upper bounds are obtained via explicit constructions based on the incidence graphs of finite projective planes, affine planes, and biaffine planes. For several specific parameter sets, the constructions are shown to meet the lower bound, establishing that they are balanced biregular cages.

Significance. If the proofs of minimality hold, the paper provides new families of cage graphs in a generalized setting. The geometric constructions are a positive aspect, as they leverage known structures with well-understood properties to achieve extremal results. This work opens a new direction in cage problems and could lead to further classifications or bounds.

minor comments (2)
  1. [Abstract] Abstract: the claim that 'some of the obtained graphs are balanced biregular cages' would be strengthened by explicitly listing the specific degree pairs and girths for which equality holds.
  2. [Introduction] The definition of 'balanced' (equal number of vertices per degree) should be stated with a formal notation (e.g., n_k = n_l) at the first appearance in the introduction to avoid ambiguity with bipartition balance.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive and accurate summary of our work on balanced biregular cages, as well as the recommendation for minor revision. The significance assessment is appreciated, particularly the recognition of the geometric constructions and their potential to open new directions in cage problems.

Circularity Check

0 steps flagged

No significant circularity; bounds and constructions are independent

full rationale

The paper defines balanced biregular cages, derives lower bounds via standard Moore-type counting arguments on vertex counts in biregular graphs of given girth and degree sequence, and obtains matching upper bounds by explicit constructions from the incidence graphs of projective, affine, and biaffine planes. These planes are external, well-studied combinatorial objects whose parameters are fixed independently of the cage problem. When a construction meets the lower bound, the equality is a genuine optimality result rather than a definitional or fitted tautology. No self-definitional steps, no predictions that reduce to fitted inputs, and any self-citations are non-load-bearing for the central claims.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The work rests on standard properties of finite projective and affine planes and their incidence graphs; no new free parameters or invented entities are introduced in the abstract.

axioms (1)
  • domain assumption Incidence graphs of projective, affine, and biaffine planes are biregular with known degrees and girth.
    Invoked to obtain the constructions and girth control.

pith-pipeline@v0.9.0 · 5384 in / 1098 out tokens · 35141 ms · 2026-05-12T01:44:48.078348+00:00 · methodology

Review history (2 revisions) →

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

32 extracted references · 32 canonical work pages

  1. [1]

    Abajo, G

    E. Abajo, G. Araujo, C. Balbuena, and M. Bendala, New small regular graphs of girth5,Discrete Math.340(2017), 1878–1888

    work page 2017

  2. [2]

    Abajo, C

    E. Abajo, C. Balbuena, M. Bendala, and X. Marcote, Improving bounds on the order of regular graphs of girth5,Discrete Math.342(2019), 2900–2910

    work page 2019

  3. [3]

    Abajo and M

    E. Abajo and M. Bendala, Regular graphs of girth5from elliptic semi planes of type C,Discrete Math.344(2021), Paper 112343

    work page 2021

  4. [4]

    Abreu, G

    M. Abreu, G. Araujo-Pardo, C. Balbuena, and D. Labbate, Families of small regular graphs of girth5,Discrete Math.312(2012), 2832–2842

    work page 2012

  5. [5]

    Araujo-Pardo, C

    G. Araujo-Pardo, C. Balbuena, P. García-Vázquez, X. Marcote, J.C. Valenzuela, On the order of({r, m};g)-cages of even girth,Discrete Math.308(2008), 2484–2491

    work page 2008

  6. [6]

    Araujo-Pardo, C

    G. Araujo-Pardo, C. Balbuena, and T. Héger, Finding small regular graphs of girths 6, 8, and 12 as subgraphs of cages,Discrete Math.310 (8)(2010), 1301-1306

    work page 2010

  7. [7]

    Araujo-Pardo G., Balbuena. C. López-Chávez G., Montejano L., Bi- regular small graphs of even girth at least 8.Aequ. Math.86(2013), 201–216. DOI 10.1007/s00010-013-0227-5

    work page doi:10.1007/s00010-013-0227-5 2013

  8. [8]

    Araujo-Pardo, G

    G. Araujo-Pardo, G. Exoo, and R. Jajcay, Small biregular graphs of even girth,Discrete Math.339(2016), 658–667. 22

    work page 2016

  9. [9]

    Araujo-Pardo, D

    G. Araujo-Pardo, D. González-Moreno, J.J. Montellano-Ballesteros, O. Serra, On upper bounds and connectivity of cages,Australasian J. Com- bin.38(2009), 221–228

    work page 2009

  10. [10]

    González-Moreno D, Mixed Cages: monotony, connectivity, and upper bounds.Discrete Math.345(2022), 112792

    Araujo-Pardo G., de la Cruz C. González-Moreno D, Mixed Cages: monotony, connectivity, and upper bounds.Discrete Math.345(2022), 112792. 1–11. https://doi.org/10.1016/j.disc.2021.112792

    work page doi:10.1016/j.disc.2021.112792 2022

  11. [11]

    A note on mixed cages of girth5,Discrete Math,349 (2), (2026), 114773

    Araujo-Pardo G., Mendoza-Cadena M. A note on mixed cages of girth5,Discrete Math,349 (2), (2026), 114773. https: //doi 10.1016/j.disc.2025.114773

    work page doi:10.1016/j.disc.2025.114773 2026

  12. [12]

    Araujo-Pardo, A

    G. Araujo-Pardo, A. Ramos-Rivera, R. Jajcay, T. Szőnyi, On a relation between bipartite biregular cages, block designs, and generalized polygons,J. Combin. Des.30No.7 (2022), 479-496. https://doi.org/10.1002/jcd.21836

    work page doi:10.1002/jcd.21836 2022

  13. [13]

    Boben, R

    M. Boben, R. Jajcay and T. Pisanski, Generalized cages,Electron. J. Combin.22(1)(2015), #P1.77

    work page 2015

  14. [14]

    W. G. Brown, On the non-existence of a type of regular graphs of girth 5,Canad. J. Math.19(1967), 644–648

    work page 1967

  15. [15]

    R. H. Bruck, Quadratic extensions of cyclic planes,Proc. Sympos.Appl. Math.10(1960), 15–44

    work page 1960

  16. [16]

    Chartrand, R.J

    G. Chartrand, R.J. Gould, S.F. Kapoor, Graphs with prescribed degree set and girth,Period. Math. Hungar.6(1981), 261–266

    work page 1981

  17. [17]

    Coolsaet, S

    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. https://houseofgraphs.org

    work page 2023

  18. [18]

    Erdős and H

    P. Erdős and H. Sachs, Reguläre Graphen gegebener Taillenweite mit minimaler Knotenzahl,Wiss. Z. Uni. Halle (Math. Nat.)12(1963), 251–257

    work page 1963

  19. [19]

    Exoo, Regular graphs of given degree and girth

    G. Exoo, Regular graphs of given degree and girth. http://ginger.indstate.edu/ge/CAGES

    work page

  20. [20]

    Exoo and R

    G. Exoo and R. Jajcay, Dynamic cage survey,Electron. J. Combin., Dynamic Survey16(2008)

    work page 2008

  21. [21]

    Exoo and R

    G. Exoo and R. Jajcay, Biregular cages of odd girth,J. Graph Theory 81, No. 1 (2016), 50–56

    work page 2016

  22. [22]

    Filipovski, On bipartite cages of excess4,Electron

    S. Filipovski, On bipartite cages of excess4,Electron. J. Combin.24(1) (2017), #P1.40. 23

    work page 2017

  23. [23]

    Filipovski, A

    S. Filipovski, A. Ramos-Rivera, and R. Jajcay, On biregular bipartite graphs of small excess,Discrete Math.342(2019), 2066–2076

    work page 2019

  24. [24]

    Funk, Girth 5 graphs from elliptic semiplanes,Note Mat.29(suppl

    M. Funk, Girth 5 graphs from elliptic semiplanes,Note Mat.29(suppl

    work page

  25. [25]

    Füredi, F

    Z. Füredi, F. Lazebnik, Á. Seress, V. A. Ustimenko and A. J. Woldar, Graphs of prescribed girth and bi-degree,J. Comb. Theory Ser. B64 (1995), 228–239

    work page 1995

  26. [26]

    T. B. Jajcayová, R. Jajcay, Gy. Kiss and I. Porupsánszki, Extremal To- tally Regular Mixed Graphs and Partially Oriented Incidence Graphs of Projective and Biaffine Planes,Ann. Comb.2025, https: //doi 10.1007/s00026-025-00788-5

    work page doi:10.1007/s00026-025-00788-5 2025

  27. [27]

    Gyürki, R

    Š. Gyürki, R. Jajcay, P. Jánoš, J. Širáň and Y. Wang, Using bi-coset graphs to construct small regular and biregular graphs, submitted for publication

    work page

  28. [28]

    L. K. Jørgensen, Girth 5 graphs from relative difference sets,Discrete Math.293(2005), 177–184

    work page 2005

  29. [29]

    Kiss and T

    Gy. Kiss and T. Szőnyi,Finite Geometries,CRC Press,Taylor & Francis Group, 2019

    work page 2019

  30. [30]

    Sachs, Regular graphs with given girth and restricted circuits,J

    H. Sachs, Regular graphs with given girth and restricted circuits,J. London Math. Soc.38(1963), 423–429

    work page 1963

  31. [31]

    G.Wegner, Asmallestgraphofgirth5andvalency5,J. Combin. Theory Ser. B14(1973), 203–208

    work page 1973

  32. [32]

    Yuansheng and W

    Y. Yuansheng and W. Liang, The minimum number of vertices with girth6and degree setD={r, m},Discrete Math.269(2003), 249-258. Gabriela Araujo-Pardo:Instituto de Matemáticas-Campus Juriquilla, Universidad Nacional Autónoma de México, C.P. 076230, Boulevard Ju- riquilla # 3001, Juriquilla, Qro., México; e-mail:garaujo@im.unam.mx György Kiss:Department of Ge...

    work page 2003