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 
and 
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,
![adj(G^k)=sum_(i=1)^k[adj(G)]^i,](/images/equations/GraphPower/NumberedEquation1.svg) |
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).
