TOPICS

# 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,

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

Adjacency Matrix, Graph Cube, Graph Square, Pósa's Theorem, Seymour Conjecture

## References

Fleischner, H. "The Square of Every Two-Connected Graph Is Hamiltonian." J. Combin. Th. Ser. B 16, 29-34, 1974.Mukhopadhyay, A. "The Square Root of a Graph." J. Combin. Th. 2, 290-295, 1967.Skiena, S. Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, 1990.

Graph Power

## Cite this as:

Weisstein, Eric W. "Graph Power." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/GraphPower.html