arxiv: 2604.20890 · v1 · submitted 2026-04-20 · 🧮 math.HO · math.CO· math.GR

Recognition: unknown

Algebraic Graph Theory

M Reza Salarian

Pith reviewed 2026-05-10 03:04 UTC · model grok-4.3

classification 🧮 math.HO math.COmath.GR

keywords algebraic graph theorystrongly regular graphsSteiner systemsautomorphism groupsPetersen graphPaley graphsSageMathpermutation groups

0 comments

The pith

This note introduces algebraic graph theory by describing strongly regular graphs, Steiner systems, automorphism groups, and their symmetry in concrete examples.

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

The paper sets out to give an accessible entry point into algebraic graph theory by covering strongly regular graphs, Steiner systems, and automorphism groups. It walks through constructions and properties of well-known graphs such as the Petersen graph, Paley graphs, Hamming graphs, and the Hoffman-Singleton graph. The focus stays on how symmetry and combinatorial structure appear in these objects and how they relate to permutation groups. SageMath examples are supplied to compute automorphism groups and invariants directly. A sympathetic reader would value the chance to see algebraic ideas applied step-by-step to recognizable graphs without needing to assemble the material from scattered sources.

Core claim

This note provides an introduction to selected topics in algebraic graph theory, including strongly regular graphs, Steiner systems, and automorphism groups. We describe constructions and properties of notable graphs such as the Petersen graph, Paley graphs, Hamming graphs, and the Hoffman-Singleton graph, with emphasis on their symmetry and combinatorial structure. Connections with permutation groups are also discussed. Computational examples using SageMath are included to illustrate key concepts and to compute automorphism groups and related invariants.

What carries the argument

Automorphism groups of graphs, which record all symmetry-preserving mappings of vertices and thereby tie combinatorial graph features to algebraic group actions.

If this is right

Graphs with rich automorphism groups can be studied and classified using tools from finite group theory.
Strongly regular graphs and Steiner systems supply explicit families where algebraic invariants such as eigenvalue spectra become computable.
SageMath scripts allow direct verification of group orders, orbits, and regularity conditions for any listed construction.
Permutation-group language unifies the description of vertex-transitive actions across different graph families.
The same symmetry viewpoint extends naturally to other distance-regular graphs built from similar combinatorial designs.

Where Pith is reading between the lines

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

The same algebraic approach could be tested on larger or infinite graphs once computational limits are addressed.
Incidence structures from Steiner systems may link directly to error-correcting codes, an application left implicit in the note.
Readers might use the provided examples as templates to generate new graphs with prescribed symmetry properties.
The emphasis on explicit computation suggests that algebraic graph theory gains clarity when theoretical claims are paired with machine verification.

Load-bearing premise

The reader already knows the basic definitions of graphs, regularity, and groups so that the constructions, properties, and SageMath code can be followed.

What would settle it

Running the SageMath commands given for the Petersen graph and checking that the computed automorphism group order matches the known value of 120 would confirm the accuracy of the computational examples.

Figures

Figures reproduced from arXiv: 2604.20890 by M Reza Salarian.

**Figure 1.1.** Figure 1.1: Two isomorphic graphs on five vertices. Proposition 1.0.1. Let φ be an isomorphism from X to Y . Then for every vertex v ∈ V (X), φ [PITH_FULL_IMAGE:figures/full_fig_p006_1_1.png] view at source ↗

**Figure 1.2.** Figure 1.2: A directed graph. Unless otherwise stated, all graphs in these notes are assumed to be finite, simple, and undirected. 1.1 Subgraphs Definition 1.1.1. A subgraph Y of a graph X is a graph with V (Y ) ⊆ V (X) and E(Y ) ⊆ E(X). If V (Y ) = V (X), then Y is called a spanning subgraph of X. Any spanning subgraph can be obtained by deleting edges from X. The number of spanning subgraphs of X is 2 |E(X)| . Def… view at source ↗

**Figure 1.3.** Figure 1.3: Original graph, spanning subgraph, and induced subgraph on vertices {1,2,3}. [PITH_FULL_IMAGE:figures/full_fig_p007_1_3.png] view at source ↗

**Figure 1.4.** Figure 1.4: The Petersen graph, labeled by 2-element subsets of [PITH_FULL_IMAGE:figures/full_fig_p015_1_4.png] view at source ↗

**Figure 1.5.** Figure 1.5: The Tutte–Coxeter graph. Vector Space Construction A more algebraic construction reveals the source of its symmetry. Consider the 3- dimensional vector space V = F 3 2 over the field F2 = {0, 1}. • The points of the Fano plane are the 1-dimensional subspaces of V . Since F2 has only one nonzero element, each 1-dimensional subspace contains exactly one nonzero vector. There are (23 − 1) = 7 such vectors, … view at source ↗

**Figure 1.6.** Figure 1.6: The Fano plane. The Coxeter Graph The Coxeter graph is a famous 3-regular (cubic) graph with 28 vertices and 42 edges. It is known for its high symmetry and interesting properties. Construction As an Induced Subgraph of K(7, 3) This construction is crucial for understanding the graph’s automorphisms. • Let K(7, 3) be the Kneser graph whose vertices are all 3-element subsets of a 7-element set P (the poin… view at source ↗

**Figure 1.7.** Figure 1.7: Coxeter graph. Proof. Girth. Since H is bipartite, all cycles have even length. Consider a 4-cycle: p1 − ℓ1 − p2 − ℓ2 − p1. This would require two distinct lines ℓ1, ℓ2 both containing two common points p1, p2, which is impossible in the Fano plane (two points lie on exactly one line). Hence no 4-cycle exists. The Fano plane contains triangles (3 points on a line), but in the bipartite Levi graph these t… view at source ↗

**Figure 1.8.** Figure 1.8: Heawood graph [PITH_FULL_IMAGE:figures/full_fig_p029_1_8.png] view at source ↗

**Figure 1.9.** Figure 1.9: Hoffman–Singleton graph. Definition 1.7.3 (Hamiltonian Graph). A graph G = (V, E) is called Hamiltonian if it contains a cycle that visits every vertex in V exactly once and returns to the starting vertex. Such a cycle is called a Hamiltonian cycle. Definition 1.7.4 (Hamiltonian Path). A Hamiltonian path in a graph G is a path that visits every vertex exactly once, but does not necessarily return to the … view at source ↗

**Figure 1.10.** Figure 1.10: A Hamiltonian path in Coxeter graph. – C5 (degree 2), – the Petersen graph (degree 3), – the Hoffman–Singleton graph (degree 7). • It is an open problem whether a Moore graph of diameter 2 and degree 57 exists. 4. Let G be a Moore graph of degree d and diameter k; that is, |V (G)| = M(d, k) := 1 + d + d(d − 1) + · · · + d(d − 1)k−1 . Show that G is a (d, g)-cage with g = 2k + 1; in other words, show tha… view at source ↗

**Figure 1.11.** Figure 1.11: Left: the Hoffman–Singleton graph with a Petersen subgraph highlighted in [PITH_FULL_IMAGE:figures/full_fig_p041_1_11.png] view at source ↗

**Figure 3.1.** Figure 3.1: The Folkman graph, the smallest semi-symmetric graph. [PITH_FULL_IMAGE:figures/full_fig_p064_3_1.png] view at source ↗

**Figure 4.1.** Figure 4.1: Inequivalent 3-arcs in the cube A graph X is s-arc transitive if it has a group G of automorphisms such that G is transitive, and the stabilizer Gu of a vertex u acts transitively on the s-arcs with initial vertex u. Theorem 4.0.1. Let X be a vertex-transitive graph and s ≥ 1. Then X is s-arc-transitive if and only if, for any vertex v, the stabilizer Aut(X)v acts transitively on the set of (s − 1)-arcs … view at source ↗

read the original abstract

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.

Desk Editor's Note private letter to a colleague

This is a basic expository note on standard algebraic graph theory topics with SageMath examples, but no new results or insights.

read the letter

The main thing to know is that this paper is an expository note introducing selected standard topics in algebraic graph theory, with no new theorems, derivations, or claims. It covers strongly regular graphs, Steiner systems, automorphism groups, and specific examples like the Petersen graph, Paley graphs, Hamming graphs, and the Hoffman-Singleton graph, plus some SageMath code for computing invariants and groups. Connections to permutation groups are mentioned as well. What it does reasonably well is organize these classic constructions and properties into one place and show how to use software to explore them in practice. The computational illustrations could save a reader time when first encountering these graphs. The soft spots are clear and expected for this type of work: everything is drawn from existing literature, so the paper adds no advance in knowledge or technique. Its usefulness depends entirely on whether the summaries are clear and the code runs without errors. The abstract and stress-test note give no sign of internal contradictions or unsupported steps, but a close check of the explanations would still be needed to confirm accuracy. This is aimed at readers who already know basic graph theory and group theory and want a compact tour with code examples, such as students or instructors. A working researcher in the area will not find material to build on or cite. I would not send it for peer review as a research contribution; it fits better as lecture notes or an informal reference.

Referee Report

0 major / 2 minor

Summary. The manuscript is an expository note that introduces selected topics in algebraic graph theory. It covers strongly regular graphs, Steiner systems, and automorphism groups, describing constructions and properties of notable graphs such as the Petersen graph, Paley graphs, Hamming graphs, and the Hoffman-Singleton graph with emphasis on symmetry and combinatorial structure. Connections to permutation groups are discussed, and SageMath examples are included to illustrate concepts and compute automorphism groups and related invariants.

Significance. If the descriptions and SageMath examples are accurate, the note could serve as a useful pedagogical resource for readers with basic graph theory and group theory background, illustrating how algebraic methods apply to concrete graphs. The computational component adds practical value for verifying properties like automorphism groups. As a purely expository work without new results or claims, its significance is primarily educational rather than advancing the research frontier.

minor comments (2)

[Computational examples section] The SageMath code examples would be more effective if sample outputs were included alongside the code to allow readers to verify results without executing the scripts themselves.
[Introduction] A brief statement of prerequisites or target audience at the outset would help readers assess whether the note matches their background.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive assessment of our expository note and the recommendation for minor revision. We appreciate the view that the manuscript, with its descriptions of strongly regular graphs, notable symmetric graphs, Steiner systems, automorphism groups, and SageMath examples, could serve as a useful pedagogical resource for readers with basic graph theory and group theory background.

Circularity Check

0 steps flagged

Expository note with no derivations or predictions

full rationale

This is a purely introductory survey of standard topics in algebraic graph theory (strongly regular graphs, Steiner systems, automorphism groups, and named graphs like Petersen and Hoffman-Singleton). It describes known constructions, properties, and supplies SageMath code for established examples. No novel theorems, parameter fits, predictions, or load-bearing derivations are present, so none of the enumerated circularity patterns can apply. All content rests on externally verifiable, pre-existing results in the field without self-referential reduction.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

This is an introductory review note with no original claims, so it introduces no free parameters, axioms, or invented entities.

pith-pipeline@v0.9.0 · 5352 in / 946 out tokens · 33169 ms · 2026-05-10T03:04:20.898481+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

17 extracted references

[1]

ifd/kis odd, then all thick vertices have the same valency
[2]

ifd/kis even, then the thick vertices have at most two distinct valencies
[3]

Proof.Choose two thick verticesvandwwithd(v, w) =k

moreover, every vertex at distancekfrom a thick vertex is itself thick. Proof.Choose two thick verticesvandwwithd(v, w) =k. Letxbe any other thick vertex ofX. Step 1:kdividesd.By Lemma 6.5.4, there exists a cycleCof length2dcontaining v,w, andx. By Lemma 6.5.5, starting atvand moving aroundC, everykth vertex is thick. In particular, the antipodev′ ofvinC(...
[4]

thek-fold subdivision of a multiple edge
[5]

Proof.Suppose first thatXhas no thick vertices

thek-fold subdivision of a thick generalized polygon. Proof.Suppose first thatXhas no thick vertices. Then every vertex has degree2, soX is simply a cycle of length2d, which is case (i). Now assumeXhas at least one thick vertex. Letkbe the minimal distance between thick vertices. By Lemma 6.5.6,kdividesd, and everykth vertex along a geodesic from a thick ...
[6]

All parameters(b i, ai, ci)thus depend only oniand not on the particular vertices: b0 =k, b i =k−1 (1≤i≤d−1), b d = 0;a i = 0 (0≤i≤d);c 1 =· · ·=c d−1 = 1, c d =k

Therefore the remainingk−1neighbors lie inΓ i+1(x), sob i =k−1. All parameters(b i, ai, ci)thus depend only oniand not on the particular vertices: b0 =k, b i =k−1 (1≤i≤d−1), b d = 0;a i = 0 (0≤i≤d);c 1 =· · ·=c d−1 = 1, c d =k. HenceXis distance–regular. The order of a thick generalized polygon satisfies certain inequalities due to Higman and Haemers. The...
[7]

Ifd= 4, thens≤t 2 andt≤s 2
[8]

Ifd= 6, thenstis a perfect square, ands≤t 3,t≤s 3
[9]

Proof.LetXbe the incidence graph of the generalizedd-gon of order(s, t)

Ifd= 8, then2stis a perfect square, ands≤t 2,t≤s 2. Proof.LetXbe the incidence graph of the generalizedd-gon of order(s, t). ThenXis connected, bipartite (points/lines), diameterd, girth2d, and semi-regular: every point lies ont+ 1lines, every line containss+ 1points. Distance–regular setup.Fix a base vertexx(say, a point). LetΓi = Γi(x)denote vertices at...
[10]

every point is incident with at least two lines and every line is incident with at least two points
[11]

given a pointxand a lineℓnot incident withx, there is a unique pointyonℓ collinear withx
[12]

block” instead of “line,

there are no ordinary4-cycles of points and lines (equivalently the incidence graph has girth8). If every line is incident with exactlys+ 1points and every point is incident with exactly t+ 1lines, we say the GQ has order(s, t). Theorem 6.6.1.Up to isomorphism there is a unique generalized quadrangle of order (2,2). Proof.Let(P,L)be a GQ of order(2,2). We...

1949
[13]

Note, however, that whent= 2, the contraction(X ′,B ′)is not a Steiner system, since it would correspond tot−1 = 1

The proof of Theorem 6.8.1 holds for allt≥2. Note, however, that whent= 2, the contraction(X ′,B ′)is not a Steiner system, since it would correspond tot−1 = 1
[14]

For instance, ifx, y∈X, then the number of blocks containing bothxandyequals the replication number in the contraction atxthat still containsy

The same argument yields a formula for the number of blocks in a Steiner system S(t, k, v)that contain a fixed set ofppoints (1≤p≤t). For instance, ifx, y∈X, then the number of blocks containing bothxandyequals the replication number in the contraction atxthat still containsy. Denoting this number byr′, one obtains r′ = (v−2)(v−3)· · ·(v−t+ 1) (k−2)(k−3)·...
[15]

infinite

The integrality of these numbers |B|, r, r ′, r (p), . . . , r (t) = 1 imposes strong arithmetic restrictions on the possible parameters(t, k, v)of a Steiner system. 146CHAPTER 6. INCIDENCE STRUCTURES Definition 6.8.3.If(X,B)and(Y,C)are Steiner systems, anisomorphismis a bijection f:X→Ysuch that B∈B⇐ ⇒f(B)∈C. An isomorphism from a system to itself is call...

1931
[16]

We denote the core ofXbyX •

There exists a homomorphism fromXtoY. We denote the core ofXbyX •. IfYis a core ofXandf:X→Yis a homomorphism, then the restrictionf|Y must be an automorphism ofY. Composingfwith the inverse of this automorphism yields a retraction fromXtoY(a homomorphism that is the identity onY). Thus, any core ofXis aretract. A graphXisχ-critical(or simplycritical) if t...
[17]

Proof.Letfbe an endomorphism ofX

inXlies in a shortest odd cycle, thenXis a core. Proof.Letfbe an endomorphism ofX. SinceXis non-bipartite, it contains an odd cycle. LetCbe a shortest odd cycle. The imagef(C)must be an odd cycle of the same length (as shortening the cycle would contradict minimality). Therefore,fis injective on C. The condition that every 2-arc lies in a shortest odd cyc...