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 (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 nodes with graph
diameter
is a complete graph . 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.

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