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
, 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:
|
(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).