Harries Graph

The Harries graph is one of the three -cage graphs, the other two being the -cage graph known as the Balaban 10-cage and the Harries-Wong graph.

The Harries graph is implemented in the Wolfram Language as GraphData["HarriesGraph"].

The Harries graph is Hamiltonian with Hamiltonian cycles. It has 678 distinct LCF notations, four of which are order 5 (illustrated above) and 674 of which are order 1. The order-5 LCF notations are [, , and .

The plots above show the adjacency matrix, incidence matrix, and graph distance matrix for the Harries graph.

Notice that the Harries graph and Harries-Wong graph are cospectral graphs, meaning neither is determined by spectrum.

The following table summarizes properties of the Harries graph.

automorphism group order	120
characteristic polynomial
chromatic number	2
claw-free	no
clique number	2
cospectral graphs names	Harries-Wong graph
determined by spectrum	no
diameter	6
distance-regular graph	no
edge chromatic number	3
edge connectivity	3
edge count	105
Eulerian	no
girth	10
Hamiltonian	yes
Hamiltonian cycle count	98304
integral graph	no
independence number	35
perfect matching graph	no
planar	no
polyhedral graph	no
radius	6
regular	yes
square-free	yes
traceable	yes
triangle-free	yes
vertex connectivity	3
vertex count	70
weakly regular graph parameters