Up

Perkel graph

There is a unique distance-regular graph with intersection array {6,5,2;1,1,3}. It has 57 vertices and spectrum 6 ((3±√5)/2)18 (−3)20. It is known as the Perkel graph. Uniqueness is due to Coolsaet & Degraer (2005).

Group

The full group of automorphisms is L2(19) with point stabilizer Alt(5).

Construction

This is the graph with vertex set Z3 x Z19 where (i,j) is joined to (i+1,k) when (k−j)3 = 26i.

For further constructions, see [BCN], p. 402.

Subgraphs

Maximal cocliques: 
there are 650145 maximal cocliques
size #
12: 1140
13: 83220
14: 375060
15: 158460
16: 29640
17: 2565
19: 60
The 60 cocliques of size 19 fall into 20 groups of 3 pairwise disjoint ones (forming a 3-coloring). The three cocliques in one 3-coloring meet a coclique in a different 3-coloring in 4, 6, 9 points.

The subgraph of the vertices at maximal distance from a given point induces a dodecahedron.

Substructures belonging to the maximal subgroups of the automorphism group:

a) A 3-coloring (partition into 3 19-cocliques). There are 20 of these, forming a single orbit. The stabilizer of one is 19:9, transitive on the vertices.

b) A vertex. There are 57 of these, forming a single orbit. The stabilizer of one is Alt(5) with vertex orbit sizes 1+6+30+20.

c) A Petersen subgraph There are 57 of these, forming a single orbit. The stabilizer of one is Alt(5) with vertex orbit sizes 5+10+12+30. The orbits of size 5 form the 57 sets of five points, pairwise at distance 3.

d) An edge. There are 171 of these, forming a single orbit. The stabilizer of one is D20 with vertex orbit sizes 2+5+10+10+10+20.

e) An antipodal triple. An antipodal triple is a triple {x,y,z} with the property that for each of the three points of the triple, the other two points are antipodes in the dodecahedron (of diameter 5) at distance 3 from the given point. There are 190 of these, forming a single orbit. The stabilizer of one is D18 with vertex orbit sizes 3+9+9+9+9+18.

Chromatic number

This graph is 3-chromatic.

Polygonal graph

This graph is a 5-gonal graph, that is, has a system S of pentagons such that each 2-claw is contained in a unique pentagon in S.

References

[BCN], Section 13.3.

K. Coolsaet and J. Degraer, A computer-assisted proof of the uniqueness of the Perkel graph, Designs, Codes and Cryptography 34 (2005) 155-171.

P. M. Neumann, Primitive permutation groups of degree 3p, preprint, 1968.

M. Perkel, Bounding the valency of polygonal graphs with odd girth, Canad. J. Math. 31 (1979) 1307-1321.