85.110.80.94 at 19:13, 9 January 2014

2014-01-09T19:13:22Z

New page

{{infobox graph
| name = Harries graph
| image = [[Image:Harries_graph.svg|220px]]
| image_caption = The Harries graph
| namesake =
| vertices = 70
| edges = 105
| automorphisms = 120 ([[Symmetric group|''S''5]])
| girth = 10
| diameter = 6
| radius = 6
| chromatic_number = 2
| chromatic_index = 3
| properties = [[Cubic graph|Cubic]] [[Cage (graph theory)|Cage]] [[Triangle-free graph|Triangle-free]] [[Hamiltonian graph|Hamiltonian]]
}}
In the [[mathematics|mathematical]] field of [[graph theory]], the '''Harries graph''' or '''Harries (3-10)-cage''' is a 3-[[regular graph|regular]] [[undirected graph]] with 70 vertices and 105 edges.<ref> {{MathWorld|urlname=HarriesGraph|title=Harries Graph}}</ref>

The Harries graph has [[chromatic number]] 2, [[chromatic index]] 3, radius 6, diameter 6, girth 10 and is [[Hamiltonian graph|Hamiltonian]]. It is also a 3-[[k-vertex-connected graph|vertex-connected]] and 3-[[k-edge-connected graph|edge-connected]] [[planar graph|non-planar]] [[cubic graph]].

The [[characteristic polynomial]] of the Harries graph is

: <math>(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. \, </math>

==History==
In 1972, A. T. Balaban published a (3-10)-[[cage graph]], a cubic graph that has as few vertices as possible for girth 10.<ref>A. T. Balaban, A trivalent graph of girth ten, J. Combin. Theory Ser. B 12, 1-5. 1972.</ref> It was the first (3-10)-cage discovered but it was not unique.<ref>Pisanski, T.; Boben, M.; Marušič, D.; and Orbanić, A. "The Generalized Balaban Configurations." Preprint. 2001. [http://citeseer.ist.psu.edu/448980.html].</ref>

The complete list of (3-10)-cage and the proof of minimality was given by O'Keefe and Wong in 1980.<ref>M. O'Keefe and P.K. Wong, A smallest graph of girth 10 and valency 3, J. Combin. Theory Ser. B 29 (1980) 91-105.</ref> There exist three distinct (3-10)-cage graphs—the [[Balaban 10-cage]], the Harries graph and the [[Harries–Wong graph]].<ref>Bondy, J. A. and Murty, U. S. R. Graph Theory with Applications. New York: North Holland, p. 237, 1976.</ref> Moreover, the Harries–Wong graph and Harries graph are [[Spectral graph theory|cospectral graphs]].

==Gallery==
<gallery>
Image:Harries graph 2COL.svg|The chromatic number of the Harries graph is 2.
Image:Harries graph 3color edge.svg|The chromatic index of the Harries graph is 3.
Image:harries_graph_alternative_drawing.svg|Alternative drawing of the Harries graph.
Image:Harries graph petersen drawing.jpg|Alternative drawing emphasizing the graph's 4 orbits.

</gallery>

== References ==
{{reflist}}

[[Category:Individual graphs]]
[[Category:Regular graphs]]

Symbolic computation - Revision history

85.110.80.94 at 19:13, 9 January 2014