Paulus Graphs


The Paulus graphs are the 15 strongly regular graphs on 25 nodes with parameters (nu,k,lambda,mu)=(25,12,5,6) and the 10 strongly regular graphs on 26 nodes with parameters (26, 10, 3, 4).

They are implemented in the Wolfram Language as GraphData[{"Paulus", {n, i}}].

The (25,15)-Paulus graph is isomorphic to the 25-Paley graph.

The 25-node Paulus graphs are cospectral, as are the 26-node Paulus graphs, so none of these is determined by spectrum.

The (26,8)-Paulus graph has the largest possible graph automorphism group order of all 26-node Paulus graphs (namely 120), and is sometimes known as the Paulus-Rozenfeld-Thompson (or PRT) graph and denoted T (Gyürki et al. 2020).

The Paulus graphs are pancyclic.

The (25,2)-, (25,4)-, and (26,10)-Paulus graphs have the apparently rather unusual property of being both integral graphs and identity graphs.

See also

Chang Graphs, Cospectral Graphs, Determined by Spectrum, Paley Graph, Paulus-Rozenfeld-Thompson Graph, Strongly Regular Graph

Explore with Wolfram|Alpha


Brouwer, A. E. "Paulus Graphs.", A. E.; Cohen, A. M.; and Neumaier, A. Distance-Regular Graphs. New York: Springer-Verlag, p. 37, "Paulus graphs (SRG(25,12,5,6)) (14 graphs, 7 pairs)." [Excludes the 25-Paley graph.] "Paulus graphs (SRG(26,10,3,4)) (10 graphs)."ürki, Š.; Klin, M.; and Ziv-Av, M. "The Paulus-Rozenfeld-Thompson Graph on 26 Vertices Revisited and Related Combinatorial Structures." In Isomorphisms, Symmetry and Computations in Algebraic Graph Theory: Pilsen, Czech Republic, October 3-7, 2016 (Ed. G. A. Jones, I. Ponomarenko, and J. Širáň). Cham, Switzerland: Springer Nature, pp. 73-154, 2020.Paulus, A. J. L. "Conference Matrices and Graphs of Order 26." Technische Hogeschool Eindhoven. Report WSK 73/06, Eindhoven, 1973.

Referenced on Wolfram|Alpha

Paulus Graphs

Cite this as:

Weisstein, Eric W. "Paulus Graphs." From MathWorld--A Wolfram Web Resource.

Subject classifications