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 L_{2}(19)
with point stabilizer Alt(5).

## Construction

This is the graph with vertex set Z_{3} x Z_{19}
where (i,j) is joined to (i+1,k) when (k−j)^{3} = 2^{6i}.
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 D_{20} 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 D_{18} 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.