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 
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,](/National_Library/20161007105358im_/http://mathworld.wolfram.com/images/equations/GraphPower/NumberedEquation1.gif) |
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).
Contact the MathWorld Team
21.80144366645
