TOPICS
Search

Harries Graph


HarriesGraph

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

The Harries graph is Hamiltonian with 98304 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 [-35,-27,27,-23,15,-15,-9,-35,23,-27,27,9,15,-15]^5 [-35,9,15,-15,23,-27,27,-35,15,-15,-9,-27,27,-23]^5, [-33,-27,27,-21,-13,13,19,29,-29,33,21,-19,-13,13]^5, and [-33,-27,27,9,-13,13,-21,29,-29,33,-13,13,-9,21]^5.

HarriesGraphMatrices

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 order120
characteristic polynomial(x-3)(x-1)^4(x+1)^4(x+3)(x^2-6)(x^2-2)(x^4-6x^2+2)^5(x^4-6x^2+3)^4(x^4-6x^2+6)^5
chromatic number2
claw-freeno
clique number2
cospectral graph namesHarries-Wong graph
determined by spectrumno
diameter6
distance-regular graphno
edge chromatic number3
edge connectivity3
edge count105
Eulerianno
girth10
Hamiltonianyes
Hamiltonian cycle count98304
integral graphno
independence number35
perfect matching graphno
planarno
polyhedral graphno
radius6
regularyes
square-freeyes
traceableyes
triangle-freeyes
vertex connectivity3
vertex count70
weakly regular parameters(70,(3),(0),(0,1))

See also

Balaban 10-Cage, Cage Graph, Cospectral Graphs, Determined by Spectrum, Harries-Wong Graph

Explore with Wolfram|Alpha

References

Pisanski, T.; Boben, M.; Marušič, D.; and Orbanić, A. "The Generalized Balaban Configurations." Preprint. 2001. http://citeseer.ist.psu.edu/448980.html.Read, R. C. and Wilson, R. J. An Atlas of Graphs. Oxford, England: Oxford University Press, p. 272, 1998.Wong, P. K. "Cages--A Survey." J. Graph Th. 6, 1-22, 1982.

Cite this as:

Weisstein, Eric W. "Harries Graph." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/HarriesGraph.html

Subject classifications