TOPICS
Search

Graph Square

DOWNLOAD Mathematica NotebookDownload Wolfram Notebook

The square of a graph is defined as its second graph power.

The square of any biconnected graph is Hamiltonian (Fleischner 1974, Skiena 1990, p. 231). Mukhopadhyay (1967) has considered "square root graphs," whose square gives a given graph G (Skiena 1990, p. 253).

Since raising any graph to the power of its graph diameter gives a complete graph, the square of any graph on n nodes with graph diameter <=2 is a complete graph K_n. Classes of such graphs include cocktail party graphs, complete graphs, complete bipartite graphs, complete tripartite graphs, dipyramid graphs, star graphs, and wheel graphs.

The following table summarizes the squares of some indexed families of graphs.

graph Ggraph square G^2
antiprism graph Ci_(2n)(1,2)circulant graph Ci_(2n)(1,2,3,4)
cycle graph C_ncirculant graph Ci_n(1,2)
empty graph K^__nempty graph K^__n
hypercube graph Q_nhalved cube graph Q_(n+1)/2
Möbius ladder M_ncirculant graph Ci_(2n)(1,2,n-1,n)

See also

Graph Cube, Graph Power, Graph Product

Explore with Wolfram|Alpha

References

Fleischner, H. "The Square of Every Two-Connected Graph Is Hamiltonian." J. Combin. Th. Ser. B 16, 29-34, 1974.Mukhopadhyay, A. "The Square Root of a Graph." J. Combin. Th. 2, 290-295, 1967.Skiena, S. Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, 1990.

Cite this as:

Weisstein, Eric W. "Graph Square." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/GraphSquare.html

Subject classifications