Pith. sign in

REVIEW 3 major objections 5 minor 29 references

On $(k,g)$-Graphs without $(g+1)$-Cycles

T0 review · 3 major / 5 minor · reviewed 2026-08-12 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read The paper pins down exact minimal orders for eight families of $k$-regular graphs of odd girth $g$ with no $g+1$-cycle, and proves lower bounds that feed the classical Cage Problem.

desk verdict Clean new extremal parameter with a solid lower bound and useful computational data; fix the abstract's false monotonicity claim and get a second implementation for the larger exact values before calling them fully certified. read the letter →

arxiv 2411.19023 v2 pith:AMUQPNTE submitted 2024-11-28 math.CO cs.DM

Leonard Chidiebere Eze , Robert Jajcay , Jorik Jooken This is my paper · ORCID
classification math.COcs.DM MSC 05C3505C85
keywords k-regulargraphsgirthcyclestructureextremalCageProblemgraphgenerationalgorithmMooreboundPair
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

This paper asks how few vertices a $k$-regular graph of girth $g$ can have when, on top of forbidding all cycles shorter than $g$, it also forbids cycles of the very next length $g+1$. It proves a Moore-type lower bound for odd $g$: every such graph has at least $M(k,2t+1)+(k-2)k(k-1)^{t-1}$ vertices, and a divisibility condition that rules out equality in some cases. It also proves that skipping two in girth lowers the extremal order by at least two, and it supplies an exhaustive generation algorithm. Running that algorithm settles eight exact values, including $n(3,7,8)=36$ and $n(3,9,10)=76$, and gives upper bounds such as $n(3,11,12)\le 272$. These orders feed the classical Cage Problem because a canonical double cover of a $(k,g,\underline{g+1})$-graph is a $k$-regular graph of girth at least $g+3$.

What carries the argument

The load-bearing object is the Moore tree $T_v(k,2t+1)$, the breadth-first tree of depth $t$ rooted at a vertex of a $(k,2t+1,\underline{2t+2})$-graph; its leaves $S$ must be joined by horizontal edges to create the girth cycles. Lemma 2 caps the number of such horizontal edges at $|S|/2=k(k-1)^{t-1}/2$, so at least $(k-2)k(k-1)^{t-1}$ edges leave the tree and attach to distinct outside vertices, generating the lower bound. The exact values are carried by an exhaustive backtracking generator that starts from the disjoint union of a Moore tree and isolated vertices, branches on one eligible edge at a time, prunes any graph with a cycle shorter than $g$ or of length $g+1$, and uses canonical forms to suppress isomorphic branches. Around this, the canonical double cover inequality $n(k,g+3)\le 2n(k,g,\underline{g+1})$ connects the new orders to the Cage Problem, and voltage lifts of a four-vertex looped base graph are used to realize the small cubic cages.

What would settle it

Generate all 3-regular graphs on 75 vertices with girth 9 and no 10-cycle using an independent method; one such graph would disprove $n(3,9,10)=76$. Alternatively, a $(3,11,12)$-graph on 143 vertices would refute Proposition 3.

Watch

Extended reading notes

Core claim

The paper's central claim is that the extremal orders $n(k,g,\underline{g+1})$ are governed by the Moore tree at a vertex, the horizontal edges among its leaves, and the edges that must leave the tree. Proposition 3 establishes that for odd girth $g=2t+1$ the order is at least the Moore bound plus $(k-2)k(k-1)^{t-1}$, and Proposition 4 gives a divisibility obstruction: equality can hold only if $4t+2$ divides a certain product built from the order and the leaf count. For $k=3$ these bounds imply $n(3,11,12)\ge 144$. The exhaustive algorithm, seeded by a Moore tree plus isolated vertices, then determines the exact values in Table 2 for eight parameter pairs, finding at most two non-isomorphic cages in each case and in several cases exactly one. The paper further proves uniqueness of the smallest $(3,6,7)$-graph with odd girth 11, resolving a 1997 conjecture, and identifies upper bounds for larger cases from voltage lifts and highly symmetric graph lists.

Load-bearing premise

The exact values in Table 2 rest on the assumption that the exhaustive generator is truly exhaustive: no partial graph thrown away by its pruning rules could have grown into a valid graph, and the supercomputer runs terminated exactly as reported; only the four smallest cases were checked against independent generators.

Editorial extensions

If this is right

  • If the orders in Table 2 are correct, then for odd $g$ the canonical double cover of each listed $(k,g,\underline{g+1})$-cage gives an explicit $k$-regular graph of girth at least $g+3$ whose order is close to the best known cage order at $g+3$.
  • The inequality $n(k,g,\underline{g+1})\le n(k,g+2,\underline{g+3})-2$ implies that skip-two girth pairs produce strictly smaller extremal orders, a monotonicity statement for the new function.
  • Combining Proposition 3 and Proposition 4 gives $n(3,11,12)\ge 144$, while the voltage-lift search gives $n(3,11,12)\le 288$ and the symmetric-graph search improves this to $n(3,11,12)\le 272$.
  • The uniqueness results identify exact small cages such as the unique $(3,5,6)$-cage on 18 vertices and the two $(3,3,4)$-cages on 10 vertices.
  • The proof of the 1997 uniqueness conjecture for the smallest $(3,6,7)$-graph of odd girth 11 closes a question that had been open since the problem was posed.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • A pattern visible in the data but not proven in the paper is that every listed extremal graph of odd girth $g$ also contains a $(g+3)$-cycle; if this is general, the canonical double cover would deliver girth exactly $g+3$, sharpening the link to the Cage Problem.
  • The divisibility obstruction of Proposition 4 is likely the first member of a family of congruence conditions; testing larger $t$ computationally could reveal whether the lower bound of Proposition 3 is ever attainable.
  • The fact that the unique $(3,7,8)$- and $(3,9,10)$-cages are both voltage lifts of the same four-vertex looped base graph suggests parameterizing this lift family for girths beyond the range currently settled.
  • The exhaustive generator is designed for forbidding one specific cycle length, but the same canonical-form and eligible-edge pruning scheme would transfer to the more general girth-pair problem of prescribing both an even and an odd shortest cycle.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 5 minor

Summary. The paper studies k-regular graphs of girth g that contain no cycles of length g+1, denoted (k,g,g+1)-graphs, and investigates the order n(k,g,g+1) of the smallest such graphs. The main theoretical results are a lower bound n(k,2t+1,2t+2) ≥ M(k,2t+1) + (k-2)k(k-1)^{t-1} (Proposition 3), a divisibility obstruction for equality in this bound (Proposition 4), and a two-step inequality n(k,g,g+1) ≤ n(k,g+2,g+3) - 2 (Theorem 1). The paper also proposes an exhaustive generation algorithm, reports exact values of n(k,g,g+1) for eight parameter pairs in Table 2, gives several upper bounds based on voltage lifts and vertex-transitive graph censuses, and uses the algorithm to prove a conjecture of Campbell on a smallest (3,6,7)-graph with odd girth 11. The lower-bound arguments are coherent and the connection to the cage problem via canonical double covers is clearly explained.

Significance. If the computational claims hold, the paper makes a solid contribution to the extremal regular graph literature: the lower bounds are new, parameter-free, and strengthen the Moore bound specifically for graphs forbidding the next cycle length; the exact values add useful data to the girth-pair problem; and the canonical double cover link gives a concrete route toward improving cage upper bounds for even girths. The paper also makes its code and generated graphs publicly available, and it includes independent verification for four of the eight exact values. The main reservations concern the completeness and independent confirmation of the larger computational entries, and an incorrect monotonicity statement in the abstract.

major comments (3)
  1. [Abstract and §1] The abstract claims that the paper establishes 'the monotonicity of the function n(k,g,g+1) with respect to increasing g', but this is false: §5.1 explicitly notes that n(k,g,g+1) > n(k,g+1,g+2) is possible for odd g, and the table itself gives n(3,3,4)=10 while n(3,4,5)=n(3,4)=6. The actual theorem, Theorem 1, is the two-step inequality n(k,g,g+1) ≤ n(k,g+2,g+3) − 2, which is not monotonicity. The abstract and introduction should be corrected to state the precise inequality and to remove the misleading monotonicity claim.
  2. [§4, Algorithm 2 and optimization 1] The completeness of the exhaustive generator is not established by the description. The recursion state consists of the graph Γ together with the set eligibleEdges, which records edges that have been rejected in earlier branches. The canonical-form pruning described in optimization 1 compares only canonical forms of Γ, not of the pair (Γ, eligibleEdges). Two states with isomorphic graphs can have different eligible-edge sets, and a completion using an edge that is still eligible in one state may be impossible in the other; pruning the second state on the basis of graph isomorphism alone could therefore discard valid (k,g,g+1)-graphs. To justify the exactness of Table 2, the paper must either prove that the eligible-edge set is determined by the graph and the deterministic branching rule, or include the full state in the isomorphism check.
  3. [§5.1 and §5.4, Table 2] The exact values for the four larger entries of Table 2 — n(3,9,10)=76, n(4,5,6)=45, n(5,3,4)=26, and n(6,3,4)=34 — rest entirely on Algorithm 1 having terminated for every order below the listed value and on its completeness. Section 5.4 independently verifies only n(3,3,4)=10, n(3,5,6)=18, n(3,7,8)=36, and n(4,3,4)=15. In particular, for (3,9,10) the lower bound of Proposition 3 leaves only the intermediate even orders 72 and 74 to be excluded, and that exclusion is not independently confirmed by the voltage-lift search of §5.2, which covers only lifts of K_{1,3}^{loop}. The paper should provide per-case termination evidence (e.g., search logs or certificates) or an independent generation run for these cases before the exact values can be taken as established.
minor comments (5)
  1. [§1] In the paragraph after equation (2), 'the order of the canonical double cover would be of order 284' should read 288, since 2 × 144 = 288.
  2. [§5.1, Table 2] The entries in the '# vertex orbits' column, such as '3 and 3' and '4 and 15', are not self-explanatory; the caption should state that these are the orbit counts of the respective non-isomorphic cages.
  3. [§5.2 and Appendix] The claim that the number of relevant voltage assignments is bounded by the number of distinct 3-element subsets of G is inaccurate: with the spanning-tree voltages fixed, a voltage assignment is an ordered triple of group elements, so the number of assignments is |G|^3, not the number of 3-element subsets. The stated bound 'at most cubic in N' remains true, but the wording should be corrected.
  4. [§4, Algorithm 2] The update function 'newEligibleEdges ← update(eligibleEdges, Γ′)' is not specified; for reproducibility, the paper should define how eligibility is updated after adding or rejecting an edge.
  5. [§5.3] The proof of Campbell's conjecture is also computational, but Section 5.4 does not mention any independent verification for this case; it would be helpful to state how the uniqueness computation was checked or to classify it with the other computational results.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the lower-bound proofs are self-contained counting arguments, and the exact values come from an explicit exhaustive generation algorithm whose completeness is a computational risk, not a circular step.

full rationale

The paper's derivation chain does not reduce to its own inputs. The main lower bound (Proposition 3) is obtained by counting horizontal edges in a Moore tree and deriving a lower bound on edges leaving its leaves; this is a parameter-free combinatorial argument against the Moore bound, not a fitted or assumed value. Proposition 4 is an independent double-counting divisibility condition. Theorem 1 gives an explicit vertex-deletion construction from a (k,g+2,g+3)-cage, with its own proof using the girth assumption on the starting graph. The exact values in Table 2 are produced by Algorithm 1, an explicitly described exhaustive generator, combined with independently established lower bounds; no target value is used as an input to derive itself. The paper explicitly acknowledges in Section 5.4 that only the four smallest cases were independently verified with alternative generators (snarkhunter and GENREG), so the larger entries depend on the algorithm's completeness and termination. That is a correctness risk about the computational claim, not a circularity: an incomplete or non-terminated search would make an entry an upper bound, but it would not mean the value was assumed. Self-citations such as [4] and [12] are published theorems by overlapping authors, but they are used only to guarantee existence of the objects under study and to justify the regular-lift construction; the paper's target values and lower bounds are not restatements of those theorems. No fitted parameter is renamed as a prediction, and no uniqueness theorem from the authors' prior work is invoked to force the choice of constructions. The canonical double cover comparisons in Table 1 are applications of known constructions to the newly determined values, not circular definitions. Overall, the mathematical derivations are self-contained and the computational claim is honestly flagged as depending on exhaustive search, so the circularity score is 0.

Assumptions & free parameters 0 free parameters · 3 assumptions · 0 invented entities

No fitted parameters or invented entities. The theoretical lower bound is parameter-free; the computational results rely on standard external tools and published existence results.

assumptions (3)
  • standard math For every k>=3 and g>=3, a (k,g,g+1)-graph exists (Boben, Jajcay, Pisanski [4]).
    Invoked in the definition of n(k,g,g+1) and in Theorem 1, which starts from a (k,g+2,g+3)-cage. This is an imported existence theorem, not derived here.
  • standard math The Moore bound M(k,g) is a lower bound on the order of any k-regular graph of girth g.
    Used as the baseline in Proposition 3 and in the elementary bound M(k,g+3)/2 <= n(k,g,g+1) in Section 2.
  • domain assumption nauty computes correct canonical forms, and the generators snarkhunter and GENREG are correct for the verified cases.
    Algorithm 1's completeness for the computed values depends on canonical-form pruning; independent cross-checks in Section 5.4 cover only four small parameter pairs.

how reviews work

0 comments
Cite this review

Pith. "Pith review of On $(k,g)$-Graphs without $(g+1)$-Cycles." pith.science (2026). https://pith.science/paper/AMUQPNTE

@misc{pith2026241119023,
  author       = {Pith},
  title        = {Pith review of: On $(k,g)$-Graphs without $(g+1)$-Cycles},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/AMUQPNTE}},
  note         = {Machine review of arXiv:2411.19023}
}
abstract

A $(k,g,\underline{g+1})$-graph is a $k$-regular graph of girth $g$ which does not contain cycles of length $g+1$. Such graphs are known to exist for all parameter pairs $k \geq 3, g \geq 3 $, and we focus on determining the orders $n(k,g,\underline{g+1})$ of the smallest $(k,g,\underline{g+1})$-graphs. This problem can be viewed as a special case of the previously studied Girth Pair Problem, the problem of finding the order of a smallest $k$-regular graph in which the length of a smallest even length cycle and the length of a smallest odd length cycle are prescribed. When considering the case of an odd girth $g$, this problem also yields results towards the Cage Problem, the problem of finding the order of a smallest $k$-regular graph of girth $g$. We establish the monotonicity of the function $n(k,g,\underline{g+1})$ with respect to increasing $g$, and present universal lower bounds for the values $n(k,g,\underline{g+1})$. We propose an algorithm for generating all $(k,g,\underline{g+1})$-graphs on $n$ vertices, use this algorithm to determine several of the smaller values $n(k,g,\underline{g+1})$, and discuss various approaches to finding smallest $(k,g,\underline{g+1})$-graphs within several classes of highly symmetrical graphs.

Figures

Figures reproduced from arXiv: 2411.19023 by the authors.

Figure 1
Figure 1. The graphs Γ (left) and Σ (right). Edges in [PITH_FULL_IMAGE:figures/full_fig_p005_1.png] view at source ↗
Figure 2
Figure 2. An example showing that a (3, 5, 6) graph cannot have a vertex x ∈ S connected by horizontal edges xu1 and xu2 to two different vertices u1 and u2 in S. The bold edges indicate a 6-cycle. Let E′ (S) be the set of edges incident to the leaves of T (k, 2t + 1), which are different from horizontal edges and different from the edges in T (k, 2t + 1); these are the edges connecting the leaves of T (k, 2t+ 1) to vertices … view at source ↗
Figure 3
Figure 3. The two (3, 3, 4)-cages on 10 vertices. The leftmost graph is also known as the tricorn [PITH_FULL_IMAGE:figures/full_fig_p012_3.png] view at source ↗
Figures from the paper (5 more)
Figure 4
Figure 4. Figure 4: The unique (3,5,6)-cage (the generalised Petersen graph GP(9,2)). n(k, g + 1, g + 2) is possible when g is odd. In fact, for the cases in [PITH_FULL_IMAGE:figures/full_fig_p012_4.png]
Figure 5
Figure 5. Figure 5: The unique (3,7,8)-cage, wherein the 9 coloured vertices in the middle are adjacent to the vertices on the three different cycles with the same colour (these edges are not drawn). In other words, the graph has edge set {aizi | z ∈ {b, c, d}, i ∈ {0, 1, . . . , 8}} ∪ {z…
Figure 6
Figure 6. Figure 6: The two (4, 3, 4)-cages on 15 vertices. The graph on the right is the line graph of the Petersen graph. graph on 4 vertices obtained by adding a loop to each leaf of the tree K1,3. We discovered that the unique (3, 7, 8)-cage and the unique (3, 9, 10)-cage are both reg…
Figure 7
Figure 7. Figure 7: The (3, 7, 8)-cage (left) and (3, 9, 10)-cage (right) are regular lifts of a voltage graph using voltage groups (Z9, +9) and (Z19, +19), respectively. We now recall a theorem by Exoo and the second author [12]: Theorem 5 (Th. 3.3 in [12]). For every graph Γ of girth g …
Figure 8
Figure 8. Figure 8: The unique smallest (3, 6, 7)-graph with odd girth 11. 5.4 Independent Verifications Since the above results rely on computations, it is very important to take extra measures that could indicate a potential bug in the implementation of the algorithm. Therefore, we trie…

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

29 extracted references · 27 canonical work pages

  1. [1]

    Balbuena, D

    C. Balbuena, D. Gonz´ alez-Moreno, J. J. Montellano-Ballesteros. A note on the upper bound and girth pair of ( k, g)-cages. Discrete Appl. Math., 161(6):853–857, 2013

    work page 2013

  2. [2]

    Balbuena, and J

    C. Balbuena, and J. Salas. On the order of graphs with a given girth pair. Discrete Math., 321:68-75, 2014

    work page 2014

  3. [3]

    H. U. Besche, B. Eick and E. A. O’Brien. A millennium project: constructing Small Groups Internat. J. Algebra Comput.12, 623–644, 2002

    work page 2002

  4. [4]

    Boben, R

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

    work page 2015

  5. [5]

    Brinkmann, J

    G. Brinkmann, J. Goedgebeur and B. D. McKay. Generation of cubic graphs. Discrete Math. Theor. Comput. Sci., 13(2), 2011

    work page 2011

  6. [6]

    C. M. Campbell. On cages for girth pair (6 , b). Discrete Math., 177:259–266, 1997

    work page 1997

  7. [7]

    Conder and P

    M. Conder and P. Dobcs´ anyi. Trivalent symmetric graphs on up to 768 vertices. J. Comb. Math. & Comb. Comp., 40:41–63, 2002

    work page 2002

  8. [8]

    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:97–107, 2023. Available at https://houseofgra phs.org/

    work page 2023

Show all 29 references
  1. [9]

    Erd˝ os and H

    P. Erd˝ os and H. Sachs: Regul¨ are Graphen gegebener Taillenweite mit minimaler Knotenzahl. Wiss. Z. Uni. Halle (Math. Nat.)12:251–257, 1963

    1963

  2. [10]

    G. Exoo. A small trivalent graph of girth 14. Electron. J. Combin.9(N3), 2002

    2002

  3. [11]

    Exoo and R

    G. Exoo and R. Jajcay. Dynamic cage survey. Electron. J. Combin., DS(16), 2013

    2013

  4. [12]

    Exoo and R

    G. Exoo and R. Jajcay. On the girth of voltage graph lifts. Europ. J. Combin., 32(4):554–562, 2011

    2011

  5. [13]

    H. Fu, K. Huang, and C. Rodger. Connectivity of cages, J. Graph Theory, 24:187–191, 1997

    1997

  6. [14]

    Goedgebeur and J

    J. Goedgebeur and J. Jooken. Exhaustive generation of edge-girth-regular graphs. Experim. Math., 1–13, 2025

    2025

  7. [15]

    Goedgebeur, J

    J. Goedgebeur, J. Jooken and T. Van den Eede. Computational methods for finding bi-regular cages. arXiv:2411.17351 [math.CO], 2024

    2024 arXiv

  8. [16]

    J. L. Gross, T. W. Tucker. Topological Graph Theory. Dover, Mineola, New York, 2001

    2001

  9. [17]

    Harary and P

    F. Harary and P. Kov´ acs. Regular graphs with given girth pair,J. Graph Theory, 7(2):209–218, 1983. 18

    1983

  10. [18]

    Jajcay, J

    R. Jajcay, J. Jooken and I. Porups´ anszki. On vertex-girth-regular graphs: (Non-)existence, bounds and enumeration. arXiv:2408.14557 [math.CO], 2024

    2024 arXiv

  11. [19]

    B. D. McKay, W. Myrvold, and J. Nadon. Fast backtracking principles applied to find new cages. In Proceedings of the Ninth Annual ACM-SIAM Symposium on Discrete Algorithms (San Francisco, CA, 1998), 188–191. ACM, New York, 1998

    1998

  12. [20]

    B. D. McKay and A. Piperno. Practical graph isomorphism, II. J. Symbolic Comput., 60:94– 112, 2014

    2014

  13. [21]

    Meringer

    M. Meringer. Fast generation of regular graphs and construction of cages. J. Graph Theory, 30(2):137—146, 1999

    1999

  14. [22]

    Sequence A006821 in the on-line encyclopedia of integer sequences

    OEIS Foundation Inc. Sequence A006821 in the on-line encyclopedia of integer sequences. https://oeis.org/A006821, 2024

    2024

  15. [23]

    Census of pentavalent arc-transitive graphs

    P. Potoˇ cnik. Current list for “Census of pentavalent arc-transitive graphs”. Available athttps: //users.fmf.uni-lj.si/potocnik/work_datoteke/AT5-Census.mgm, 2024

    2024

  16. [24]

    Potoˇ cnik

    P. Potoˇ cnik. A list of 4-valent 2-arc-transitive graphs and finite faithful amalgams of index (4, 2). Europ. J. Combin., 30(5):1323–1336, 2009

    2009

  17. [25]

    Potoˇ cnik, P

    P. Potoˇ cnik, P. Spiga and G. Verret. Cubic vertex-transitive graphs on up to 1280 vertices. J. Symbolic Comput., 50:465–477, 2013

    2013

  18. [26]

    Potoˇ cnik, P

    P. Potoˇ cnik, P. Spiga and G. Verret. Bounding the order of the vertex-stabiliser in 3-valent vertex transitive and 4-valent arc-transitive graphs. J. Combin. Theory Ser. B, 111:148–180, 2015

    2015

  19. [27]

    N. Sauer. Extremaleigenschaften regul¨ arer Graphen gegebenerTaillenweite, I and II, Sitzungs- berichte ¨Osterreich. Akad. Wiss. Math. Natur. Kl., S-B II, 176:9–25 & 27–43, 1967

    1967

  20. [28]

    Wilson and P

    S. Wilson and P. Potoˇ cnik. Recipes for edge-transitive tetravalent graphs.The Art of Discrete and Appl. Math., 3(1), 2020. 19 Appendix Computational Details for Determining nloop K1,3 (3, g, g+ 1) The most straightforward approach for computingnKloop 1,3 (3, g, g+ 1) would b...

    2020

  21. [29]

    All the above considerations make it possible to compute nKloop 1,3 (3, g, g+ 1) much more efficiently than n(3, g, g+ 1) can be computed

    (for an arbitrary but fixed ordering of the group elements, where e′ 1 and e′ 2 represent the darts corresponding to e1 and e2 in the orientation of K loop 1,3 , respectively). All the above considerations make it possible to compute nKloop 1,3 (3, g, g+ 1) much more efficient...

Pith tools

Reviewed August 12, 2026 · model on record in the stance chip above.