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 is illustrated above in a number of embeddings (e.g., Knuth 2008, p. 14).
It has 12 distinct (directed) Hamiltonian cycles, corresponding to the unique order-4 LCF notation .
It is a unit-distance graph, as shown above in a unit-distance embedding (Harborth and Möller 1994).
The minimal planar integral embeddings of the cubical graph, illustrated above, has maximum edge length of 2 (Harborth et al. 1987). They are also graceful (Gardner 1983, pp. 158 and 163-164).
can be constructed as the graph expansion of with steps 1 and 1, where is a path graph. Excising an edge of the cubical graph gives the prism 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 the Wolfram Language as GraphData["CubicalGraph"].
It is a distance-regular graph with intersection array , and therefore also a Taylor graph.
The graph square of the cubical graph is the skeleton of the 16-cell.
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).
A certain construction involving the cubical graph gives an infinite number of connected vertex-transitive graphs that have no Hamilton decomposition (Bryant and Dean 2014).
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 |