The cubical graph is the Platonic graph corresponding to the connectivity of the cube. It is isomorphic to the generalized Petersen graph , bipartite Kneser graph , 4-crossed prism graph, crown graph , grid graph , hypercube graph , and prism graph .

It hs 12 distinct (directed) Hamiltonian cycles, corresponding to the unique order-4 LCF notation .

Several symmetrical circular embeddings of this graph are illustrated in the second figure above.

It can be constructed as the graph expansion of with steps 1 and 1, where is a path graph.

The cubical graph has 8 nodes, 12 edges, vertex connectivity 3, edge connectivity 3, graph diameter 3, graph radius 3, and girth 4. The cubical graph is implemented in Mathematica as GraphData["CubicalGraph"].

It is a distance-regular graph with intersection array , and therefore also a Taylor graph.

Its line graph is the cuboctahedral graph.

The maximum number of nodes in a cubical graph that induce a cycle is six (Danzer and Klee 1967; Skiena 1990, p. 149).

The plots above show the adjacency, incidence, and graph distance matrices for the cubical graph.

The following table summarizes some properties of the cubical graph.

property	value
automorphism group order	48
characteristic polynomial
chromatic number	2
chromatic polynomial
claw-free	no
clique number	2
graph complement name	8-quartic graph 2
determined by spectrum	yes
diameter	3
distance-regular graph	yes
dual graph name	octahedral graph
edge chromatic number	3
edge connectivity	3
edge count	12
Eulerian	no
girth	4
Hamiltonian	yes
Hamiltonian cycle count	12
Hamiltonian path count	144
integral graph	yes
independence number	4
intersection array
line graph	no
line graph name	cuboctahedral graph
perfect matching graph	no
planar	yes
polyhedral graph	yes
polyhedron embedding names	cube
radius	3
regular	yes
spectrum
square-free	no
traceable	yes
triangle-free	yes
vertex connectivity	3
vertex count	8

Bondy, J. A. and Murty, U. S. R. Graph Theory with Applications. New York: North Holland, p. 234, 1976.

Danzer, L. and Klee, V. "Lengths of Snakes in Boxes." J. Combin. Th. 2, 258-265, 1967.

Read, R. C. and Wilson, R. J. An Atlas of Graphs. Oxford, England: Oxford University Press, p. 266, 1998.

Royle, G. "F008A." http://www.csse.uwa.edu.au/~gordon/foster/F008A.html.

Skiena, S. Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, 1990.

Wolfram, S. A New Kind of Science. Champaign, IL: Wolfram Media, p. 1032, 2002.

CITE THIS AS:

Weisstein, Eric W. "Cubical Graph." From MathWorld--A Wolfram Web Resource. http://mathworld.wolfram.com/CubicalGraph.html