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,

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