The graph power 
,
or 
th power of a graph 
, is a graph with the same set of vertices
as 
and an edge between two vertices iff they are distinct and there is a path
of length at most 
between them (Skiena 1990, p. 229). The 
th element of the 
th power of the adjacency matrix
of 
counts walks
of length 
between vertices 
and 
,
which may repeat vertices and edges.
Graph powers are implemented in the Wolfram
Language as GraphPower[g,
k].
The 
th power of a cycle
graph 
is known as a cycle power graph.
For a positive integer 
, put ![B=sum_(i=1)^(k)[adj(G)]^i](/images/equations/GraphPower/Inline15.svg)
, which counts walks
of lengths 1 through 
.
The adjacency matrix of the graph power is obtained
by replacing its positive off-diagonal entries by 1 and setting its diagonal entries
to zero:
![[adj(G^k)]_(uv)={1 if u!=v and B_(uv)>0; 0 otherwise.](/images/equations/GraphPower/NumberedEquation1.svg) |
(1)
|
Raising a connected 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).
