Graph Power
The 
th power of a graph 
is a graph with the same set of vertices as 
and an edge between two vertices iff there is a path of length at most 
between them (Skiena 1990, p. 229). Since a path of length two between vertices 
and 
exists for every vertex 
such that ![<span style=]()
{u,w}" src="https://mathworld.wolfram.com/images/equations/GraphPower/Inline8.svg" style="height:22px; width:46px" /> and ![<span style=]()
{w,v}" src="https://mathworld.wolfram.com/images/equations/GraphPower/Inline9.svg" style="height:22px; width:44px" /> are edges in 
, the square of the adjacency matrix of 
counts the number of such paths. Similarly, the 
th element of the 
th power of the adjacency matrix of 
gives the number of paths of length 
between vertices 
and 
. Graph powers are implemented in the Wolfram Language as GraphPower[g, k].
The graph 
th power is then defined as the graph whose adjacency matrix given by the sum of the first 
powers of the adjacency matrix,
which counts all paths of length up to 
(Skiena 1990, p. 230).
Raising any graph to the power of its graph diameter gives a complete graph. 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).
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.
