The distance spectrum of the bipartite double cover of strongly regular graphs

S.Morteza Mirafzal

arxiv: 2510.02400 · v3 · submitted 2025-10-01 · 🧮 math.CO

The distance spectrum of the bipartite double cover of strongly regular graphs

S.Morteza Mirafzal This is my paper

Pith reviewed 2026-05-18 10:48 UTC · model grok-4.3

classification 🧮 math.CO

keywords strongly regular graphsbipartite double coverdistance spectrumdistance matrixgraph eigenvaluesspectral graph theorygraph parameters

0 comments

The pith

The distance spectrum of the bipartite double cover of a strongly regular graph is explicitly determined from the graph's parameters.

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

This paper establishes a direct link between the parameters of a strongly regular graph G and the distance spectrum of its bipartite double cover B(G). By deriving explicit formulas, it shows how the distance eigenvalues of B(G) can be calculated using only the order, degree, and intersection numbers of G. A reader would care because this simplifies the analysis of distance properties in these graphs, which relate to how paths and connections behave in the larger structure. The result applies to any strongly regular graph without needing extra conditions.

Core claim

For a strongly regular graph G with parameters (n, k, a, c), the bipartite double cover B(G) has a distance spectrum that is determined explicitly from these parameters. The paper demonstrates a close relationship between the spectrum of G and the distance spectrum of B(G), providing closed-form expressions for the distance eigenvalues and their multiplicities according to the parameters of G.

What carries the argument

The bipartite double cover B(G) of the strongly regular graph G, whose distance matrix is expressed using the adjacency properties and parameters of G.

If this is right

The distance eigenvalues of B(G) are given by explicit formulas involving the parameters n, k, a, c of G.
All distance eigenvalues and their multiplicities can be computed without constructing or analyzing the cover graph explicitly.
The result holds uniformly for every strongly regular graph.
Properties such as the diameter or connectivity of B(G) follow directly from the derived spectral data.

Where Pith is reading between the lines

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

The same parameter-based approach could be tested on concrete families such as the 5-cycle or lattice graphs to verify the formulas in practice.
Similar spectral relations might be investigated for other graph products or covers beyond the bipartite double.
The result may connect to broader questions about when distance spectra of derived graphs remain simple.

Load-bearing premise

The distance matrix of the bipartite double cover admits a closed-form spectral description solely in terms of the parameters of the strongly regular graph.

What would settle it

Direct computation of the distance spectrum for a specific small strongly regular graph such as the Petersen graph with parameters (10,3,0,1) and checking whether the values match the predicted closed-form expressions.

read the original abstract

A strongly regular graph with parameters $(n,d,a,c)$ is a $d$-regular graph of order $n$, in which every pair of adjacent vertices has exactly $a$ common neighbor(s) and every pair of nonadjacent vertices has exactly $c$ common neighbor(s). Let $n$ be the number of vertices of the graph $G=(V,E)$. The distance matrix $D=D(G)$ of $G$ is an $n \times n $ matrix with the rows and columns indexed by $V$ such that $D_{uv} = d_{G}(u, v)=d(u,v)$, where $d_{G}(u, v)$ is the distance between the vertices $u$ and $v$ in the graph $G$. In this paper, we are interested in determining the distance spectrum of the bipartite double cover of the family of strongly regular graphs. In other words, let $G=(V,E)$ be a strongly regular graph with parameters $(n,k,a,c)$. We show that there is a close relationship between the spectrum of $G$ and the distance spectrum of $B(G)$, where $B(G)$ is the double cover of $G$. We explicitly determine the distance spectrum of the graph $B(G)$, according to the spectrum of $G$. In fact, according to the parameters of the graph $G$.

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

The paper derives an explicit formula for the distance spectrum of the bipartite double cover of any strongly regular graph, written in terms of the input parameters.

read the letter

The key takeaway is that this paper derives an explicit formula for the distance spectrum of the bipartite double cover of a strongly regular graph, expressed using the parameters of the original graph. The authors define B(G) in the usual way as two copies of the vertices with edges crossing according to the edges in G. They then classify pairs of vertices in B(G) according to whether they are in the same copy or different copies, and according to the adjacency relation in G. Because G is strongly regular, the number of common neighbors is constant in each case, which implies that the shortest path lengths, i.e., the distances, are the same for all pairs of a given type. This uniformity means the distance matrix can be written as a sum of the adjacency matrices of the relations in the lifted scheme. Its spectrum then follows directly from the eigenvalues of the adjacency matrix of G or from the parameters (n, k, a, c). This is a straightforward but useful calculation. The reasoning relies only on the association scheme properties that define strongly regular graphs, and it does not introduce extra conditions. The result is reproducible from the given data. A soft spot is the limited generality. The formula is tied to this specific family and this cover; it does not extend to arbitrary graphs or to other matrix functions like the Seidel matrix. The paper might also benefit from listing the actual eigenvalues in a theorem statement rather than leaving them implicit in the relation to the spectrum of G. Overall, the work is for researchers who study spectra of graphs constructed from strongly regular ones. A reader who has worked with distance-regular graphs or covers will see the value immediately. I would recommend sending this to peer review. The argument is internally consistent and the combinatorial setup is standard, so referees can focus on verifying the distance calculations and the final eigenvalue expressions.

Referee Report

1 major / 2 minor

Summary. The manuscript claims that for any strongly regular graph G with parameters (n, k, a, c), the distance spectrum of its bipartite double cover B(G) is explicitly determined by the parameters of G (or equivalently by the spectrum of G). It establishes a relationship between the spectrum of G and the distance spectrum of B(G) by classifying vertex pairs in B(G) according to the relations in G and deriving distances from the walk-count recurrence of the adjacency matrix.

Significance. If the derivation holds, the result supplies a closed-form, parameter-based description of the distance eigenvalues of B(G). This is a strength: the approach uses the 2-class association scheme of G to obtain uniform distances for each combinatorial type in B(G) and then expresses the distance matrix as a linear combination of the scheme basis matrices, whose spectrum is known from that of G. The manuscript thereby delivers an explicit, falsifiable spectral formula without additional assumptions on G beyond strong regularity.

major comments (1)

[Main theorem / §3] The central derivation in the main theorem (presumably §3 or the statement following the definition of B(G)) treats distances in B(G) as constant on each of the six combinatorial types (same/different copy crossed with the three relations of G). While this follows from the association scheme, the manuscript should explicitly record the smallest m such that the m-step walk count is positive for the non-adjacent different-copy case, using the standard recurrence for A^m in terms of the parameters (n, k, a, c).

minor comments (2)

[Abstract / Introduction] The abstract states both 'according to the spectrum of G' and 'according to the parameters of the graph G'; the manuscript should clarify in the introduction which form of the final eigenvalue list is presented (the parameter form is the stronger claim).
A small worked example (e.g., the 5-cycle or the Petersen graph) would make the explicit spectrum formula immediately verifiable and should be added after the main theorem.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for their positive evaluation of the manuscript and for the constructive suggestion regarding the main theorem. We have revised the paper to address the comment explicitly.

read point-by-point responses

Referee: [Main theorem / §3] The central derivation in the main theorem (presumably §3 or the statement following the definition of B(G)) treats distances in B(G) as constant on each of the six combinatorial types (same/different copy crossed with the three relations of G). While this follows from the association scheme, the manuscript should explicitly record the smallest m such that the m-step walk count is positive for the non-adjacent different-copy case, using the standard recurrence for A^m in terms of the parameters (n, k, a, c).

Authors: We agree that an explicit computation of the smallest m strengthens the exposition. In the revised manuscript we have added, within the proof of the main result in Section 3, the standard three-term recurrence for the entries of A^m (expressed solely in terms of n, k, a, c) and applied it to the non-adjacent different-copy pairs. This shows that the (u^+, v^-) entry of A^m first becomes positive at m = 3 and remains zero for m = 1, thereby confirming that the distance is exactly 3 with no shorter path. revision: yes

Circularity Check

0 steps flagged

No significant circularity; derivation uses external parameters of G as input

full rationale

The paper derives the distance spectrum of the bipartite double cover B(G) for a strongly regular graph G with given parameters (n,k,a,c). These parameters determine the association scheme, allowing distances in B(G) to be computed uniformly from walk counts via powers of the adjacency matrix of G. The resulting distance matrix of B(G) is expressed as a linear combination of the scheme's basis matrices, whose spectrum follows directly from the known spectrum of G. The spectrum of G is treated as external given data rather than fitted or redefined within the paper. No self-definitional steps, fitted predictions renamed as results, or load-bearing self-citations appear in the derivation chain. The approach is a standard explicit calculation in spectral graph theory and remains self-contained against the combinatorial properties of strongly regular graphs.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The result rests on the standard definition of strongly regular graphs and the standard construction of the bipartite double cover; no free parameters or new entities are introduced in the abstract.

axioms (1)

domain assumption G is a strongly regular graph with parameters (n, k, a, c)
The distance spectrum formula is stated to depend on these parameters and the spectrum of G.

pith-pipeline@v0.9.0 · 5773 in / 1211 out tokens · 37338 ms · 2026-05-18T10:48:02.080794+00:00 · methodology

discussion (0)

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

IndisputableMonolith/Foundation/AlexanderDuality.lean alexander_duality_circle_linking unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

Spec(D) = {(5n)^1, (4λ1−4)^m1, … , 0^{n−1}, (4k−n−4)^1} (Theorem 2.3)

What do these tags mean?

matches: The paper's claim is directly supported by a theorem in the formal canon.
supports: The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends: The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses: The paper appears to rely on the theorem as machinery.
contradicts: The paper's claim conflicts with a theorem or certificate in the canon.
unclear: Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

27 extracted references · 27 canonical work pages · 1 internal anchor

[1]

Distance spectra of graphs: a survey, Linear Algebra Appl

Aouchiche M, Hansen P. Distance spectra of graphs: a survey, Linear Algebra Appl. 458 (2014), 301-386

work page 2014
[2]

A survey on integral graphs

Bali´aska K, Cvetkovi´cD, Radosavljevi´cZ, Simi´cS, Stevanovi´cD. A survey on integral graphs. Publ. Elektroteh. Fak., Univ. Beogr., Ser. Mat. 13 (2002), 42–65

work page 2002
[3]

Strongly Regular Graphs with No Triangles

Biggs N. Strongly regular graphs with no triangles. arXiv preprint arXiv:0911.2160, (2009)

work page internal anchor Pith review Pith/arXiv arXiv 2009
[4]

Distance-Regular Graphs, Springer- Verlag, New York, (1989)

Brouwer A.E, Cohen A.M, Neumaier A. Distance-Regular Graphs, Springer- Verlag, New York, (1989)

work page 1989
[5]

A construction of directed strongly reg- ular graphs with parameters (63,11,8,1,2)

Brouwer, A.E, Crnkovic, D, Svob, A. A construction of directed strongly reg- ular graphs with parameters (63,11,8,1,2). Discrete Math. 347, 114146 (2024)

work page 2024
[6]

DQ-integral and DL-integral generalized wheel graphs, Indian Journal of Pure and Applied Mathematics (2025): 1-12

Chai Y, Wang L, Zhou Y. DQ-integral and DL-integral generalized wheel graphs, Indian Journal of Pure and Applied Mathematics (2025): 1-12

work page 2025
[7]

An introduction to the theory of graph spectra, Cambridge University Press, (2010)

Cvetkovic D, Rowlinson P, Simic S. An introduction to the theory of graph spectra, Cambridge University Press, (2010)

work page 2010
[8]

Algebraic Graph Theory, Springer, (2001)

Godsil C, Royle G. Algebraic Graph Theory, Springer, (2001)

work page 2001
[9]

Which graphs have integral spectra?, In Graphs and Combinatorics, (eds

Harary F, Schwenk A.J. Which graphs have integral spectra?, In Graphs and Combinatorics, (eds. R. Bari and F. Harary), (Proc. Capital Conf., George Washington Univ., Washington, D.C., (1973), Lecture Notes in Mathematics 406, Springer-Verlag, Berlin (1974), 45-51

work page 1973
[10]

Distance integral Cayley graphs over abelian groups and dicyclic groups, J

Huang J, Li S.C. Distance integral Cayley graphs over abelian groups and dicyclic groups, J. Algebraic Combin. 53 (2021) 921-943

work page 2021
[11]

On determining the distance spectrum of a class of distance integral graphs, J

Kogani R, Mirafzal S.M. On determining the distance spectrum of a class of distance integral graphs, J. Algebr. Syst, 10(2) (2023), 299–308

work page 2023
[12]

A survey on distance spectra of graphs, Adv

Lin H, Shu J, Xue J, Zhang Y. A survey on distance spectra of graphs, Adv. Math. (China) 50(1) (2021) 29-76

work page 2021
[13]

Linear Algebra (Vol

Lipschutz S, Abellanas L, Ontalba C.M. Linear Algebra (Vol. 2). Madrid: McGraw-Hill, (1992)

work page 1992
[14]

A new class of integral graphs constructed from the hypercube, Linear Algebra Appl

Mirafzal S.M. A new class of integral graphs constructed from the hypercube, Linear Algebra Appl. 558 (2018) 186-194

work page 2018
[15]

The automorphism group of the bipartite Kneser graph, Proceedings-Mathematical Sciences, (2019), doi.org/10.1007/s12044-019-0477- 9

Mirafzal S.M. The automorphism group of the bipartite Kneser graph, Proceedings-Mathematical Sciences, (2019), doi.org/10.1007/s12044-019-0477- 9

work page doi:10.1007/s12044-019-0477- 2019
[16]

On the automorphism groups of connected bipartite irre- ducible graphs, Proc

Mirafzal S.M. On the automorphism groups of connected bipartite irre- ducible graphs, Proc. Math. Sci. (2020). https://doi.org/10.1007/s12044-020- 0589-1. The distance spectrum of the bipartite double cover of strongly ...13

work page doi:10.1007/s12044-020- 2020
[17]

Some remarks on the square graph of the hypercube

Mirafzal S.M. Some remarks on the square graph of the hypercube. Ars Mathematica Contemporanea Vol. 23 No. 2 (2023)

work page 2023
[18]

The line graph of the crown graph is distance integral, Linear and Multilinear Algebra 71, no

Mirafzal S.M. The line graph of the crown graph is distance integral, Linear and Multilinear Algebra 71, no. 4 (2023): 662-672

work page 2023
[19]

On the distance eigenvalues of design graphs, Ricerche mat 73, 2759–2769 (2024)

Mirafzal S.M. On the distance eigenvalues of design graphs, Ricerche mat 73, 2759–2769 (2024). https://doi.org/10.1007/s11587-023-00794-w

work page doi:10.1007/s11587-023-00794-w 2024
[20]

The distance spectrum of the line graph of the crown graph, arXiv:2508.07202v1

Mirafzal S.M. The distance spectrum of the line graph of the crown graph, arXiv:2508.07202v1

work page arXiv
[21]

The distance spectrum of regular bipartite graphs of diameter 3, Submitted

Mirafzal S.M. The distance spectrum of regular bipartite graphs of diameter 3, Submitted

work page
[22]

A Brief Introduction to Spectral Graph Theory, EMS Publishing House, Zuerich, (2018)

Nica B. A Brief Introduction to Spectral Graph Theory, EMS Publishing House, Zuerich, (2018)

work page 2018
[23]

On spectral spread of generalized distance matrix of a graph, Linear Multilinear Algebra 603: 1-19, (2020)

Pirzada S, Ganie H.A, Rather B A, Ul Shaban R. On spectral spread of generalized distance matrix of a graph, Linear Multilinear Algebra 603: 1-19, (2020)

work page 2020
[24]

Sabidussi G, Vertex-transitive graphs. Monatsh. Math. 68. 426–438 (1964)

work page 1964
[25]

Distance and adjacency spectra and eigenspaces for three (di) graph lifts: A unified approach, Linear Algebra and its Applications

Wu Y, Zhang X, Feng L, Wu T. Distance and adjacency spectra and eigenspaces for three (di) graph lifts: A unified approach, Linear Algebra and its Applications. (2023) Sep 1;672:147-81

work page 2023
[26]

Perfect matching and distance spectral radius in graphs and bipartite graphs

Zhang Y, Lin H. Perfect matching and distance spectral radius in graphs and bipartite graphs. Discrete Applied Mathematics (2021), 304, pp.315-322

work page 2021
[27]

DL-integral and DQ-integraln-Cayley graphs

Zou L, Wu Y, Feng L. DL-integral and DQ-integraln-Cayley graphs. Applied Mathematics and Computation (2025), 489, p.129178

work page 2025

[1] [1]

Distance spectra of graphs: a survey, Linear Algebra Appl

Aouchiche M, Hansen P. Distance spectra of graphs: a survey, Linear Algebra Appl. 458 (2014), 301-386

work page 2014

[2] [2]

A survey on integral graphs

Bali´aska K, Cvetkovi´cD, Radosavljevi´cZ, Simi´cS, Stevanovi´cD. A survey on integral graphs. Publ. Elektroteh. Fak., Univ. Beogr., Ser. Mat. 13 (2002), 42–65

work page 2002

[3] [3]

Strongly Regular Graphs with No Triangles

Biggs N. Strongly regular graphs with no triangles. arXiv preprint arXiv:0911.2160, (2009)

work page internal anchor Pith review Pith/arXiv arXiv 2009

[4] [4]

Distance-Regular Graphs, Springer- Verlag, New York, (1989)

Brouwer A.E, Cohen A.M, Neumaier A. Distance-Regular Graphs, Springer- Verlag, New York, (1989)

work page 1989

[5] [5]

A construction of directed strongly reg- ular graphs with parameters (63,11,8,1,2)

Brouwer, A.E, Crnkovic, D, Svob, A. A construction of directed strongly reg- ular graphs with parameters (63,11,8,1,2). Discrete Math. 347, 114146 (2024)

work page 2024

[6] [6]

DQ-integral and DL-integral generalized wheel graphs, Indian Journal of Pure and Applied Mathematics (2025): 1-12

Chai Y, Wang L, Zhou Y. DQ-integral and DL-integral generalized wheel graphs, Indian Journal of Pure and Applied Mathematics (2025): 1-12

work page 2025

[7] [7]

An introduction to the theory of graph spectra, Cambridge University Press, (2010)

Cvetkovic D, Rowlinson P, Simic S. An introduction to the theory of graph spectra, Cambridge University Press, (2010)

work page 2010

[8] [8]

Algebraic Graph Theory, Springer, (2001)

Godsil C, Royle G. Algebraic Graph Theory, Springer, (2001)

work page 2001

[9] [9]

Which graphs have integral spectra?, In Graphs and Combinatorics, (eds

Harary F, Schwenk A.J. Which graphs have integral spectra?, In Graphs and Combinatorics, (eds. R. Bari and F. Harary), (Proc. Capital Conf., George Washington Univ., Washington, D.C., (1973), Lecture Notes in Mathematics 406, Springer-Verlag, Berlin (1974), 45-51

work page 1973

[10] [10]

Distance integral Cayley graphs over abelian groups and dicyclic groups, J

Huang J, Li S.C. Distance integral Cayley graphs over abelian groups and dicyclic groups, J. Algebraic Combin. 53 (2021) 921-943

work page 2021

[11] [11]

On determining the distance spectrum of a class of distance integral graphs, J

Kogani R, Mirafzal S.M. On determining the distance spectrum of a class of distance integral graphs, J. Algebr. Syst, 10(2) (2023), 299–308

work page 2023

[12] [12]

A survey on distance spectra of graphs, Adv

Lin H, Shu J, Xue J, Zhang Y. A survey on distance spectra of graphs, Adv. Math. (China) 50(1) (2021) 29-76

work page 2021

[13] [13]

Linear Algebra (Vol

Lipschutz S, Abellanas L, Ontalba C.M. Linear Algebra (Vol. 2). Madrid: McGraw-Hill, (1992)

work page 1992

[14] [14]

A new class of integral graphs constructed from the hypercube, Linear Algebra Appl

Mirafzal S.M. A new class of integral graphs constructed from the hypercube, Linear Algebra Appl. 558 (2018) 186-194

work page 2018

[15] [15]

The automorphism group of the bipartite Kneser graph, Proceedings-Mathematical Sciences, (2019), doi.org/10.1007/s12044-019-0477- 9

Mirafzal S.M. The automorphism group of the bipartite Kneser graph, Proceedings-Mathematical Sciences, (2019), doi.org/10.1007/s12044-019-0477- 9

work page doi:10.1007/s12044-019-0477- 2019

[16] [16]

On the automorphism groups of connected bipartite irre- ducible graphs, Proc

Mirafzal S.M. On the automorphism groups of connected bipartite irre- ducible graphs, Proc. Math. Sci. (2020). https://doi.org/10.1007/s12044-020- 0589-1. The distance spectrum of the bipartite double cover of strongly ...13

work page doi:10.1007/s12044-020- 2020

[17] [17]

Some remarks on the square graph of the hypercube

Mirafzal S.M. Some remarks on the square graph of the hypercube. Ars Mathematica Contemporanea Vol. 23 No. 2 (2023)

work page 2023

[18] [18]

The line graph of the crown graph is distance integral, Linear and Multilinear Algebra 71, no

Mirafzal S.M. The line graph of the crown graph is distance integral, Linear and Multilinear Algebra 71, no. 4 (2023): 662-672

work page 2023

[19] [19]

On the distance eigenvalues of design graphs, Ricerche mat 73, 2759–2769 (2024)

Mirafzal S.M. On the distance eigenvalues of design graphs, Ricerche mat 73, 2759–2769 (2024). https://doi.org/10.1007/s11587-023-00794-w

work page doi:10.1007/s11587-023-00794-w 2024

[20] [20]

The distance spectrum of the line graph of the crown graph, arXiv:2508.07202v1

Mirafzal S.M. The distance spectrum of the line graph of the crown graph, arXiv:2508.07202v1

work page arXiv

[21] [21]

The distance spectrum of regular bipartite graphs of diameter 3, Submitted

Mirafzal S.M. The distance spectrum of regular bipartite graphs of diameter 3, Submitted

work page

[22] [22]

A Brief Introduction to Spectral Graph Theory, EMS Publishing House, Zuerich, (2018)

Nica B. A Brief Introduction to Spectral Graph Theory, EMS Publishing House, Zuerich, (2018)

work page 2018

[23] [23]

On spectral spread of generalized distance matrix of a graph, Linear Multilinear Algebra 603: 1-19, (2020)

Pirzada S, Ganie H.A, Rather B A, Ul Shaban R. On spectral spread of generalized distance matrix of a graph, Linear Multilinear Algebra 603: 1-19, (2020)

work page 2020

[24] [24]

Sabidussi G, Vertex-transitive graphs. Monatsh. Math. 68. 426–438 (1964)

work page 1964

[25] [25]

Distance and adjacency spectra and eigenspaces for three (di) graph lifts: A unified approach, Linear Algebra and its Applications

Wu Y, Zhang X, Feng L, Wu T. Distance and adjacency spectra and eigenspaces for three (di) graph lifts: A unified approach, Linear Algebra and its Applications. (2023) Sep 1;672:147-81

work page 2023

[26] [26]

Perfect matching and distance spectral radius in graphs and bipartite graphs

Zhang Y, Lin H. Perfect matching and distance spectral radius in graphs and bipartite graphs. Discrete Applied Mathematics (2021), 304, pp.315-322

work page 2021

[27] [27]

DL-integral and DQ-integraln-Cayley graphs

Zou L, Wu Y, Feng L. DL-integral and DQ-integraln-Cayley graphs. Applied Mathematics and Computation (2025), 489, p.129178

work page 2025