Up

Paulus-Rozenfeld graphs

Paulus (1973) found the conference matrices of order 25 and the two-graphs of order 26 without doing an exhaustive search. Rozenfeld (1973) did an exhaustive search and found the same graphs. They find that up to isomorphism there are 15 strongly regular graphs with parameters v = 25, k = 12, λ = 5, μ = 6 (and spectrum 121 212 (−3)12), and 10 strongly regular graphs with parameters v = 26, k = 10, λ = 3, μ = 4 (and spectrum 101 213 (−3)12).

These parameter sets are related: a strongly regular graph with parameters (26,10,3,4) is member of the switching class of a regular two-graph, and if one isolates a point by switching, and deletes it, the result is a strongly regular graph with parameters (25,12,5,6). Among these graphs are the Latin square graphs of order 5 on 25 vertices, and the complements of the block graphs of the two Steiner triple systems STS(13) on 26 vertices.

The only one among the graphs on 25 vertices with a transitive group is Paley(25). None of the graphs on 26 vertices has a transitive group.

Regular two-graphs on 26 vertices

There are 4 regular two-graphs on 26 vertices. Some properties:

name group size children
A 6 16,26,33,43,53,63,7,8
B 72 912,1012,11,12
C 39 1313,1413
D 15600 1526

Here the 26 children of a regular two-graph on 26 vertices are the serial numbers of the conference graphs on 25 vertices obtained by switching a point isolated.

Conference graphs on 25 vertices

There are 15 conference graphs on 25 vertices. Some properties:

name group size two-graph complement max cliques comments
P25.01 1 A P25.02 37,474,53  
P25.02 1 A P25.01 35,474,53  
P25.03 2 A P25.04 38,472,53  
P25.04 2 A P25.03 38,472,53  
P25.05 2 A P25.06 34,474,53  
P25.06 2 A P25.05 38,474,53  
P25.07 6 A P25.08 314,468,53  
P25.08 6 A P25.07 314,468,53  
P25.09 6 B P25.10 354,458,53  
P25.10 6 B P25.09 354,458,53  
P25.11 72B P25.12 336,464,53  
P25.12 72B P25.11 384,44,515 LS(5)
P25.13 3 C P25.14 33,475,53  
P25.14 3 C P25.13 31,475,53  
P25.15 600 D P25.15 3100,515 Paley(25)

There are two main classes of Latin squares of order 5. One gives Paley(25), the other is labeled here with LS(5).

Strongly regular graphs with parameters (26,10,3,4)

There are 10 strongly regular graphs with parameters (26,10,3,4). Some properties:

name group size two-graph max cliques max cocliques comments
P26.01 1 A 3130 4115,576,61  
P26.02 2 A 3130 4116,576,61  
P26.03 2 A 3122,42 4100,581,61  
P26.04 6 A 3122,42 4104,581,61  
P26.05 6 A 398,48 4164,524,613 STS(13)
P26.06 4 B 390,410 4136,570,63  
P26.07 6 B 382,412 4124,575,63  
P26.08 3 C 3126,41 495,581,61  
P26.09 39 C 378,413 4104,539,613 STS(13)
P26.10 120 D 390,410 4210,512,613  

References:

A. J. L. Paulus, Conference matrices and graphs of order 26, Technische Hogeschool Eindhoven, report WSK 73/06, Eindhoven, 1973, 89 pp.

M. Z. Rozenfeld, The construction and properties of certain classes of strongly regular graphs, Uspehi Mat. Nauk 28 (1973) 197-198.

See also Ted Spence's page and the Notebook on Wolfram's page.