"The" octahedral graph is the 6-node 12-edge Platonic graph having the connectivity of the octahedron. It is isomorphic to the circulant graph  . Several
embeddings of this graph are illustrated above.
It is implemented in Mathematica
as GraphData["OctahedralGraph"].
The octahedral graph has 6 nodes, 12 edges, vertex connectivity 4, edge connectivity
4, graph diameter 2, graph radius 2, and girth
3. It is the unique 6-node quartic
graph, and is also symmetric.
It has chromatic polynomial
and chromatic number 3. It is an integral graph with graph spectrum  .
Its automorphism group is
of order  .
The octahedral graph is the line graph
of the tetrahedral graph.
The plots above show the adjacency, incidence, and graph distance matrices for the octahedral graph.
The following table summarizes some properties of the octahedral graph.
| property | value | | automorphism group order | 48 | | characteristic polynomial |  | | chromatic
number | 3 | | chromatic
polynomial |  | | circulant graph |  | | claw-free | yes | | clique number | 3 | | graph
complement name | 3-ladder rung graph | | determined by spectrum | yes | | diameter | 2 | | distance-regular
graph | yes | | dual graph
name | cubical
graph | | edge chromatic number | 4 | | edge connectivity | 4 | | edge count | 12 | | Eulerian | yes | | girth | 3 | | Hamiltonian | yes | | Hamiltonian cycle count | 32 | | Hamiltonian path count | 240 | | integral graph | yes | | independence number | 2 | | line graph | yes | | perfect matching graph | no | | planar | yes | | polyhedral graph | yes | | polyhedron embedding names | octahedron, tetrahemihexahedron | | radius | 2 | | regular | yes | | spectrum |  | | square-free | no | | strongly
regular parameters |  | | traceable | yes | | triangle-free | no | | vertex connectivity | 4 | | vertex count | 6 |
Confusingly, the term "octahedral graph" is also used to refer to a polyhedral graph on eight nodes.
There are 257 topologically distinct octahedral graphs, as first enumerated by Kirkman
(1862-1863) and Hermes (1899ab, 1900, 1901; Federico 1969; Duijvestijn and Federico
1981). The cubical graph is an
octahedral graph.
Bondy, J. A. and Murty, U. S. R. Graph Theory with Applications. New York: North Holland,
p. 234, 1976.
Duijvestijn, A. J. W. and Federico, P. J. "The Number of Polyhedral
(3-Connected Planar) Graphs." Math. Comput. 37, 523-532, 1981.
Federico, P. J. "Enumeration of Polyhedra: The Number of 9-Hedra."
J. Combin. Th. 7, 155-161, 1969.
Grünbaum, B. Convex Polytopes. New York: Wiley, pp. 288 and 424,
1967.
Hermes, O. "Die Formen der Vielflache. I." J. reine angew. Math. 120,
27-59, 1899a.
Hermes, O. "Die Formen der Vielflache. II." J. reine angew. Math. 120,
305-353, 1899b.
Hermes, O. "Die Formen der Vielflache. III." J. reine angew. Math. 122,
124-154, 1900.
Hermes, O. "Die Formen der Vielflache. IV." J. reine angew. Math. 123,
312-342, 1901.
Kirkman, T. P. "Application of the Theory of the Polyhedra to the Enumeration and Registration of Results." Proc. Roy. Soc. London 12, 341-380,
1862-1863.
Read, R. C. and Wilson, R. J. An Atlas of Graphs. Oxford, England: Oxford University
Press, p. 266, 1998.
| 
Contact the MathWorld Team
