REVIEW 4 major objections 4 minor 1 cited by
Geodesic transitive graphs of small valency
T0 review · 4 major / 4 minor · reviewed 2026-08-07 · deepseek-v4-flash
Pith's one-line read The paper proves a complete classification: a connected graph of valency 2–13 is geodesic transitive if and only if it is one of the graphs listed in Tables 1–11, except for seven explicitly enumerated graphs.
desk verdict Solid classification paper; the seven-exception list is the real content, and the main risk is the unversioned external catalogue it inherits completeness from. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The argument rides on two ingredients. First, every geodesic transitive graph is distance transitive, so the universe of candidates is the known catalogue of distance transitive graphs of valency at most 13 from [4, Section 7.5], together with the graph data in the online repository [1]. Second, Lemma 2.4 gives a stabilizer-theoretic criterion: a graph is $(s+1)$-geodesic transitive exactly when it is $s$-arc transitive and the stabilizer of an $s$-geodesic $(u_0, \ldots, u_s)$ is transitive on the set $\Gamma(u_s) \cap \Gamma_{s+1}(u_0)$ of vertices one step past the endpoint that lie one step farther from $u_0$. The paper feeds each candidate into this criterion using the computational software Magma, while the infinite families in Section 2.2, including $\mathrm{AG}(2,q)$ minus a parallel class, are handled by explicit automorphism arguments.
What would settle it
Find a connected distance transitive graph of valency at most 13 that is not isomorphic to any graph in Tables 1–11 and is geodesic transitive, or show that one of the seven graphs in Lemma 3.1 is in fact geodesic transitive by exhibiting an automorphism group transitive on all $i$-geodesics for some $i$ at which the paper claims it fails; both checks can be attempted with the provided Magma code and the online repository of distance-regular graphs.
Extended reading notes
Core claim
Theorem 1.2 states that a connected graph of valency $k$ with $2 \le k \le 13$ is geodesic transitive if and only if it is isomorphic to one of the graphs listed in Tables 1–11, with the exception of the seven graphs enumerated in Lemma 3.1. Equivalently, among all distance transitive graphs of valency at most 13, exactly seven are distance transitive but not geodesic transitive: the Paley graphs $P(q)$ for $q = 13, 17, 25$, and the graphs $G_{22,6}$, $G_{64,8}$, $G_{68,12}$, $G_{280,9}$ constructed in Examples 2.20–2.23. The classification therefore pins down exactly where the two symmetry notions diverge for small valency.
Load-bearing premise
The proof assumes the published catalogue of all distance transitive graphs of valency at most 13 is complete and matches the graph data used in the computations; if a distance transitive graph is missing from that catalogue, the classification could be incomplete.
Editorial extensions
If this is right
- There is now a complete, checkable list of all geodesic transitive graphs of valency 2 through 13; any such graph found outside Tables 1–11 would contradict Theorem 1.2.
- The seven exceptions give a finite, explicit family of graphs where distance transitivity does not lift to geodesic transitivity, providing concrete test cases for the distinguishing mechanism.
- The classification confirms that most small distance transitive graphs are in fact geodesic transitive, so the gap between the two notions is rare at small valency.
- The stabilizer criterion and computational pipeline can be rerun directly on any newly discovered distance transitive graph to decide geodesic transitivity.
- The family $\mathrm{AG}(2,q)$ minus a parallel class is established as geodesic transitive for all prime powers $q$, extending the known examples of geodesic transitive graphs.
Reading between the lines
- If the external catalogue used as input is, as the paper assumes, the exhaustive list of distance transitive graphs of valency at most 13, then the same verification pipeline could be pushed to valency 14 or 15 whenever the catalogue is extended; the bottleneck is the catalogue, not the criterion.
- The seven exceptions cluster at valencies 6, 8, 9, 12, and 13, which suggests the failure of geodesic transitivity is tied to particular local structures such as intersection arrays with large $a_i$ values rather than to valency alone; this is a guess, not a claim of the paper.
- One could test the robustness of the census by recomputing geodesic transitivity of each listed graph with an independent solver, or by verifying that the graph data in the online repository [1] coincides exactly with the monograph's list [4].
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper classifies connected geodesic transitive graphs of valency at most 13. The main result, Theorem 1.2, states that a connected graph of valency k (2 ≤ k ≤ 13) is geodesic transitive if and only if it appears in Tables 1–11, excluding exactly seven graphs listed in Lemma 3.1. The proof uses the known classification of distance transitive graphs of valency at most 13 from Brouwer–Cohen–Neumaier [4], together with Magma computations that determine geodesic transitivity for each graph in that catalogue. The paper also proves that several infinite families (Hamming graphs, folded cubes, Johnson graphs, Odd graphs, Grassmann graphs, doubled Grassmann graphs, classical generalized polygons, and AG(2,q) minus a parallel class) are geodesic transitive, and it identifies seven distance transitive graphs of valency at most 13 that are not geodesic transitive: the Paley graphs P(13), P(17), P(25) and the graphs G_{22,6}, G_{64,8}, G_{68,12}, G_{280,9}.
Significance. If the classification is correct, it provides a complete census of geodesic transitive graphs of small valency and settles a natural question raised by the recent literature on s-geodesic transitive graphs. The hand-checked parts are sound: the proofs of Propositions 2.7–2.13 and Lemma 2.15 are explicit, and the reduction to checking one geodesic via Corollary 2.5 is valid for arc transitive graphs. The paper also gives useful examples of distance transitive but not geodesic transitive graphs. The main weakness is that the 'only if' direction inherits completeness from an unversioned external catalogue and from Magma runs whose code, as printed, is not runnable and whose input data are not fully supplied. Several table entries are clearly mislabeled, which reduces confidence in the computational verification. These issues are fixable, but they are load-bearing for the seven-exception claim.
major comments (4)
- [Theorem 1.2 and §3] The 'only if' direction of Theorem 1.2 depends entirely on the completeness of the list of distance transitive graphs of valency at most 13 in [4, Section 7.5] and on graph data downloaded from the online repository [1]. The paper does not pin a version or snapshot of [1], does not re-derive the [4] list, and does not provide a script that reconstructs Tables 1–11 from a fixed source and verifies that every catalogue graph appears in the tables. If a distance transitive graph is absent from the repository, or if a repository entry does not match the corresponding graph in the monograph (for instance, because [1] is a database of distance-regular rather than distance-transitive graphs), then the 'exactly seven graphs' statement is incomplete. The authors should supply a versioned copy of the data, a reconstruction script, or an independent verification of the correspondence between [4], [1], and the tables.
- [§3.1 Magma code] The Magma code printed in §3.1 is not a runnable program and therefore does not make the computational results reproducible. For example, 'Sphere(u,d)' and 'Geodesic(u,i)' are called with signatures that do not match Magma's graph functions, which require the graph as an argument, and the line 'a:=Index(V1,SetToSequence(N)[1])' assumes that N is nonempty without a guard. In addition, the function checks vertex transitivity but not arc transitivity, so it does not implement Corollary 2.5 as stated unless the input is already known to be distance transitive, and no such check or input restriction is enforced. Since the GT column and Lemma 3.1 are established by these computations, the authors need to provide corrected, tested code together with the input graph data for every table entry and logs of the runs.
- [Tables 2, 7, and 8] Several table entries are internally inconsistent, which undermines confidence in the table-generation pipeline. Table 2 lists a valency-4 graph as 'K4' with intersection array {4;1} and automorphism group S5; these data identify K5, not K4. Table 7 lists 'H(2,4)' with valency 9 and intersection array {9,4;1,6}, although H(2,4) has valency 6 (the row presumably concerns the complement of H(2,4) and should be labeled accordingly). Table 8 contains two rows both named 'J(7,2)' with different intersection arrays {10,4;1,4} and {10,6;1,6}; at most one of these can be the Johnson graph J(7,2). These errors do not by themselves refute Theorem 1.2, but they show that the mapping from [4]/[1] to the tables was not checked mechanically, and they must be corrected before the classification can be considered reliable.
- [§3.2, G_n,k entries] Many rows in Tables 1–11 refer to graphs denoted G_{n,k} (or superscripted variants) for which no explicit construction or adjacency data are provided in the paper. Examples 2.16–2.23 give orbital constructions for a handful of exceptional graphs, but the majority of the G_{n,k} entries are only identified by name, automorphism group, and intersection array. Consequently, a reader cannot independently verify the GT column for these entries without reconstructing the graphs from the repository [1] or from the monograph [4]. The authors should provide either explicit constructions, a complete set of graph files, or a script that generates every listed graph from a stated source.
minor comments (4)
- [Lemma 2.15 proof] In the proof of Lemma 2.15, the text refers to 'the parameter b_4 = 1', but b_4 is not defined for an intersection array of length four; the intended statement is b_3 = 1, since the diameter is 4 and b_i is indexed from 0 to 3.
- [Lemma 2.15 statement] Lemma 2.15 states the intersection array {q, q-1, q-1, 1; 1, 1, q-1, q} for all prime powers q, but this array encodes diameter 4, whereas the paper earlier notes that AG(2,2) is isomorphic to C4, which has diameter 2. The lemma should explicitly exclude q=2 or treat this case separately.
- [§2.2, AG(2,q)] The sentence 'Clearly, AG(2,q) ∼= C4' should read 'AG(2,2) ∼= C4'; as written it is false for general q.
- [Tables 1–11] The table headers call the lists 'the distance transitive graphs of valency k', but the tables also contain entries with GT=N (for example, P(13) in Table 4). It would be clearer to state explicitly that the tables list all distance transitive graphs from [4] of the given valency and that the GT column records whether each is geodesic transitive.
Circularity Check
No substantive circularity: the geodesic-transitivity classification is a direct computation over an external distance-transitive catalogue, and the author's self-citations are not load-bearing.
full rationale
The claimed derivation is not circular. Theorem 1.2 uses the implication geodesic transitive implies distance transitive to inherit the catalogue of all distance-transitive graphs of valency at most 13 from Brouwer-Cohen-Neumaier [4, Section 7.5] and the repository [1]. For each graph in that external catalogue, the paper either cites an independent family-level proof (Propositions 2.7 to 2.14 and the self-contained Lemma 2.15 for AG(2,q)) or runs Magma on the graph's adjacency data. The seven non-geodesic-transitive exceptions in Lemma 3.1 are outputs of that check, not inputs: Proposition 2.14(2), citing [21] and [17], settles the Paley graphs, and the remaining G22,6, G64,8, G280,9 and G68,12 are singled out by computation and listed with GT=N in the tables. No fitted parameter is used, no quantity defined in terms of the target property is fed into the check, and no uniqueness assertion is imported from the author's own prior work. The self-citation [18] appears in the introduction and in Proposition 2.7's reference cluster, but geodesic transitivity of Hamming graphs is also supported by the independent references [20] and [21], so the self-citation is not load-bearing; [19] is cited only in a survey sentence. Non-circular caveats exist: completeness inherits the unversioned external catalogue [4]/[1], Table 2 labels a valency-4 graph as K4 although its intersection array {4;1} and automorphism group S5 identify it as K5, and the printed Magma code appears to check Neighbours(...) meet Sphere(u,i) rather than the Sphere(u,i+1) set required by Corollary 2.5. These are reproducibility and correctness risks, not circularity.
Assumptions & free parameters
assumptions (3)
- domain assumption The enumeration of all distance transitive graphs of valency at most 13 in Brouwer-Cohen-Neumaier [4, Section 7.5] is complete and correct.
- domain assumption Magma's computations of automorphism groups, stabilizers, orbits, and geodesics are correct for the graphs considered.
- domain assumption The graphs referenced from the online repository [1] are the same graphs as those in [4, Section 7.5].
Cite this review
Pith. "Pith review of Geodesic transitive graphs of small valency." pith.science (2026). https://pith.science/paper/CJHJZGB4
@misc{pith2026250604670,
author = {Pith},
title = {Pith review of: Geodesic transitive graphs of small valency},
year = {2026},
howpublished = {\url{https://pith.science/paper/CJHJZGB4}},
note = {Machine review of arXiv:2506.04670}
}
abstract
For a graph $\Gamma$, the {\em distance} $d_\Gamma(u,v)$ between two distinct vertices $u$ and $v$ in $\Gamma$ is defined as the length of the shortest path from $u$ to $v$, and the {\em diameter} $\mathrm{diam}(\Gamma)$ of $\Gamma$ is the maximum distance between $u$ and $v$ for all vertices $u$ and $v$ in the vertex set of $\Gamma$. For a positive integer $s$, a path $(u_0,u_1,\ldots,u_{s})$ is called an {\em $s$-geodesic} if the distance of $u_0$ and $u_s$ is $s$. The graph $\Gamma$ is said to be {\em distance transitive} if for any vertices $u,v,x,y$ of $\Ga$ such that $d_\Ga(u,v)=d_\Ga(x,y)$, there exists an automorphism of $\Gamma$ that maps the pair $(u,v)$ to the pair $(x,y)$. Moreover, $\Gamma$ is said to be {\em geodesic transitive} if for each $i\leq \mathrm{diam}(\Ga)$, the full automorphism group acts transitively on the set of all $i$-geodesics. In the monograph [Distance-Regular Graphs, Section 7.5], the authors listed all distance transitive graphs of valency at most $13$. By using this classification, in this paper, we provide a complete classification of geodesic transitive graphs with valency at most $13$. As a result, there are exactly seven graphs of valency at most $13$ that are distance transitive but not geodesic transitive.
Forward citations
Cited by 1 Pith paper
-
Finite $s$-geodesic transitive graphs under certain girths
For s≥5, every connected (G,s)-geodesic transitive graph of girth 2s-2 or 2s-1 either has a normal quotient of the same girth, or is the Foster graph covering the Tutte 8-cage; in the quasiprimitive case G is almost simple.
Reference graph
Works this paper leans on
- [1]
-
[4]
A.E. Brouwer, A.M. Cohen, A. Neumaier, Distance-Regular Graphs, Springer Berlin, Heidelberg, 1989.https://doi.org/10.1007/978-3-642-74341-2
-
[2]
Biggs, Algebraic Graph Theory, Cambridge University Press, New York, 1974.https://doi
N.L. Biggs, Algebraic Graph Theory, Cambridge University Press, New York, 1974.https://doi. org/10.1017/CBO9780511608704
- [3]
-
[5]
P. J. Cameron, C. E. Praeger, On 2-arc transitive graphs of girth 4, J. Combin. Theory Ser. B 35 (1983) 1–11.https://doi.org/10.1016/0095-8956(83)90075-8
-
[6]
B. P. Corr, W. Jin, C. Schneider, Finite 2-distance transitive graphs, J. Graph Theory 86 (2017) 78–91.https://doi.org/10.1002/jgt.22112
-
[7]
Conway, R.T
J.H. Conway, R.T. Curtis, S.P. Norton, R.A. Parker, R.A. Wilson, Atlas of Finite Groups: Maximal Subgroups and Ordinary Characters for Simple Groups, Oxford University Press, Eynsham, 1985
1985
-
[8]
A. Devillers, M. Giudici, C.H. Li, C.E. Praeger, Locallys-distance transitive graphs, J. Graph Theory 69 (2012) 176–197.https://doi.org/10.1002/jgt.20574
Show all 35 references
-
[9]
Devillers, W
A. Devillers, W. Jin, C.H. Li, C.E. Praeger, Line graphs and geodesic transitivity, Ars Math. Contemp. 6 (2013) 13–20.https://doi.org/10.26493/1855-3974.248.aae
2013 doi
-
[10]
Devillers, W
A. Devillers, W. Jin, C.H. Li, C.E. Praeger, Local 2-geodesic transitivity and clique graphs, J. Combin. Theory Ser. A 120 (2013) 500–508.https://doi.org/10.1016/j.jcta.2012.10.004
2013 doi
-
[11]
Devillers, W
A. Devillers, W. Jin, C.H. Li, C.E. Praeger, On normal 2-geodesic transitive Cayley graphs, J. Algebr. Comb. 39 (2014) 903–918.https://doi.org/10.1007/s10801-013-0472-7
2014 doi
-
[12]
Devillers, W
A. Devillers, W. Jin, C.H. Li, C.E. Praeger, Finite 2-geodesic transitive graphs of prime valency, J. Graph Theory 80 (2015) 18–27.https://doi.org/10.1002/jgt.21835
2015 doi
-
[13]
Dixon, B
J.D. Dixon, B. Mortimer, Permutation Groups, Graduate Texts in Mathematics 163, Springer- Verlag, New York, 1996
1996
-
[14]
S. F. Du, A. Malniˇ c and D. Maruˇ siˇ c, Classification of 2-arc-transitive dihedrants, J. Combin. Theory Ser. B 98 (2008), 1349–1372.https://doi.org/10.1016/j.jctb.2008.02.007
2008 doi
-
[15]
R. Q. Feng, P. C. Hua, A new family of Geodesic transitive graphs, Discrete Math. 341 (2018) 2700–2707.https://doi.org/10.1016/j.disc.2018.06.020
2018 doi
-
[16]
Feng, J.-X
Y.-Q. Feng, J.-X. Zhou, Y.-T. Li, Pentavalent symmetric graphs of order twice a prime power, Discrete Math. 339 (2016) 2640–2651.https://doi.org/10.1016/j.disc.2016.05.008
2016 doi
-
[17]
Godsil, G.F
C.D. Godsil, G.F. Royle, Algebraic Graph Theory, Springer, New York, Berlin, Heidelberg, 2001
2001
-
[18]
Huang, Y.-Q
J.-J. Huang, Y.-Q. Feng, J.-X. Zhou, F.-G. Yin, Two-geodesic transitive graphs of orderp n with n≤3, J. Combin. Theory Ser. A, 202 (2024), 105814.https://doi.org/10.1016/j.jcta.2023. 105814
2024 doi
-
[19]
Huang, Y.-Q
J.-J. Huang, Y.-Q. Feng, K.-S. Wang, J.-X. Zhou, The classification of 3-geodesic transitive but not 3-arc transitive tetravalent graphs, submitted
-
[20]
A. A. Ivanov, C. E. Praeger, On finite affine 2-arc transitive graphs, Eur. J. Comb. 14 (1993) 421–444.https://doi.org/10.1006/eujc.1993.1047Get
1993
-
[21]
W. Jin, A. Devillers, C.H. Li, C.E. Praeger, On geodesic transitive graphs, Discrete Math. 338 (2015) 168–173.https://doi.org/10.1016/j.disc.2014.11.005
2015 doi
-
[22]
Jin, Finite 3-geodesic transitive but not 3-arc transitive graphs, Bull
W. Jin, Finite 3-geodesic transitive but not 3-arc transitive graphs, Bull. Aust. Math. Soc. 91 (2015) 183–190.https://doi.org/10.1017/S0004972714000690
2015 doi
-
[23]
Jin, Finite 2-geodesic-transitive graphs of valency 9, Util
W. Jin, Finite 2-geodesic-transitive graphs of valency 9, Util. Math., 98 (2015) 271–281
2015
-
[24]
Jin, Finite 2-geodesic-transitive graphs of valency twice a prime, European J
W. Jin, Finite 2-geodesic-transitive graphs of valency twice a prime, European J. Combin. 49 (2015) 117–125.https://doi.org/10.1016/j.ejc.2015.03.002
2015 doi
-
[25]
Jin, Finite 2-geodesic transitive graphs of valency 3p, Ars Combin
W. Jin, Finite 2-geodesic transitive graphs of valency 3p, Ars Combin. 120 (2015) 417–425
2015
-
[26]
Jin, The pentavalent three-geodesic-transitive graphs, Discrete Math
W. Jin, The pentavalent three-geodesic-transitive graphs, Discrete Math. 341 (2018) 1344–1349 https://doi.org/10.1016/j.disc.2018.02.009
2018 doi
-
[27]
W. Jin, W. J. Liu, S. J. Xu, Two-geodesic-transitive graphs of valency six, Discrete Math. 340 (2017) 192–200.https://doi.org/10.1016/j.disc.2016.08.008. GEODESIC TRANSITIVE GRAPHS OF SMALL V ALENCY 19
2017 doi
-
[28]
Jin, C.E
W. Jin, C.E. Praeger, Normal quotients of diameter at most two of finite three-geodesic-transitive graphs, J. Combin. Theory Ser. A 178 (2021) 105349.//doi.org/10.1016/j.jcta.2020.105349
2021
-
[29]
Li, The finite vertex-primitive and vertex-biprimitives-transitive graphs fors≥4, Trans
C.H. Li, The finite vertex-primitive and vertex-biprimitives-transitive graphs fors≥4, Trans. Amer. Math. Soc. 353 (2001) 3511–3529.https://doi.org/10.1090/S0002-9947-01-02768-4
2001 doi
-
[30]
R. E. A. C. Paley, On orthogonal matrices, J. Math. Phys. 12 (1933), 311–320.https://doi.org/ 10.1002/sapm1933121311
1933 doi
-
[31]
Praeger, An O’Nan-Scott theorem for finite quasiprimitive permutation groups and an appli- cation to 2-arc transitive graphs, J
C.E. Praeger, An O’Nan-Scott theorem for finite quasiprimitive permutation groups and an appli- cation to 2-arc transitive graphs, J. London Math. Soc. 47 (1993) 227–239.https://doi.org/10. 1112/jlms/s2-47.2.227
1993
-
[32]
Tutte, A family of cubical graphs, Proc
W.T. Tutte, A family of cubical graphs, Proc. Camb. Philos. Soc. 43 (1947) 459–474.https: //doi.org/10.1017/S0305004100023720
1947 doi
-
[33]
Weiss, The nonexistence of 8-transitive graphs, Combinatorica 1 (1981), 309–311.https:// doi.org/10.1007/BF02579337
R. Weiss, The nonexistence of 8-transitive graphs, Combinatorica 1 (1981), 309–311.https:// doi.org/10.1007/BF02579337
1981 doi
-
[34]
Weiss, Distance-transitive graphs and generalized polygons, Arch
R. Weiss, Distance-transitive graphs and generalized polygons, Arch. Math 45 (1985), 186–192. https://doi.org/10.1007/BF01270491
1985 doi
-
[35]
Zhou, A solution of Li-Xia’s problem ons-arc-transitive solvable Cayley graphs, J
J.X. Zhou, A solution of Li-Xia’s problem ons-arc-transitive solvable Cayley graphs, J. Combin. Theory Ser. B, 149 (2021) 147–160.https://doi.org/10.1016/j.jctb.2021.02.002. Jun-Jie Huang, School of Mathematical Sciences, Laboratory of Mathematics and Complex Systems, MOE, Bei...
2021 doi
Reviewed August 7, 2026 · model on record in the stance chip above.
Discussion (0). Sign in to comment.