TOPICS
Search

Cubical Graph


CubicalGraphEmbeddings

The cubical graph is the Platonic graph corresponding to the connectivity of the cube. It is isomorphic to the generalized Petersen graph GP(4,1), bipartite Kneser graph H(4,1), 4-crossed prism graph, crown graph S_3^0, grid graph G_(2,2,2), hypercube graph Q_3, and prism graph Y_4. 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 [3,-3]^4.

CubicalGraphUnitDistance

It is a unit-distance graph, as shown above in a unit-distance embedding (Harborth and Möller 1994).

CubicalGraphMinimalPlanarIntegralDrawing

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).

Q_3 can be constructed as the graph expansion of 4P_2 with steps 1 and 1, where P_2 is a path graph. Excising an edge of the cubical graph gives the prism graph Y_3.

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 {3,2,1;1,2,3}, 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).

CubicalGraphMatrices

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.

propertyvalue
automorphism group order48
characteristic polynomial(x-3)(x-1)^3(x+1)^3(x+3)
chromatic number2
chromatic polynomial(x-1)x(x^6-11x^5+55x^4-159x^3+282x^2-290x+133)
claw-freeno
clique number2
graph complement name8-quartic graph 2
determined by spectrumyes
diameter3
distance-regular graphyes
dual graph nameoctahedral graph
edge chromatic number3
edge connectivity3
edge count12
Eulerianno
girth4
Hamiltonianyes
Hamiltonian cycle count12
Hamiltonian path count144
integral graphyes
independence number4
intersection array{3,2,1;1,2,3}
line graphno
line graph namecuboctahedral graph
perfect matching graphno
planaryes
polyhedral graphyes
polyhedron embedding namescube
radius3
regularyes
spectrum(-3)^1(-1)^31^33^1
square-freeno
traceableyes
triangle-freeyes
vertex connectivity3
vertex count8

See also

Bidiakis Cube, Bislit Cube, Cube, Distance-Regular Graph, Dodecahedral Graph, Folded Cube Graph, Halved Cube Graph, Hypercube Graph, Icosahedral Graph, Integral Graph, Octahedral Graph, Platonic Graph, Tesseract Graph, Tetrahedral Graph

Explore with Wolfram|Alpha

References

Bondy, J. A. and Murty, U. S. R. Graph Theory with Applications. New York: North Holland, p. 234, 1976.Bryant, D. and Dean, M. "Vertex-Transitive Graphs that have no Hamilton Decomposition." 25 Aug 2014. http://arxiv.org/abs/1408.5211.Danzer, L. and Klee, V. "Lengths of Snakes in Boxes." J. Combin. Th. 2, 258-265, 1967.Gardner, M. "Golomb's Graceful Graphs." Ch. 15 in Wheels, Life, and Other Mathematical Amusements. New York: W. H. Freeman, pp. 152-165, 1983.Harborth, H. and Möller, M. "Minimum Integral Drawings of the Platonic Graphs." Math. Mag. 67, 355-358, 1994.Harborth, H.; Kemnitz, A.; Möller, M.; and Süssenbach, A. "Ganzzahlige planare Darstellungen der platonischen Körper." Elem. Math. 42, 118-122, 1987.Knuth, D. E. The Art of Computer Programming, Volume 4, Fascicle 0: Introduction to Combinatorial Functions and Boolean Functions.. Upper Saddle River, NJ: Addison-Wesley, p. 14, 2008.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. https://mathworld.wolfram.com/CubicalGraph.html

Subject classifications