The k th power of a graph G is a graph with the same set of vertices as G and an edge between two vertices iff there is a path of length at most k between them. Since a path of length two between vertices u and v exists for every vertex w such that {u, w} and {w, v} are edges in G, the square of the adjacency matrix of G counts the number of such paths. Similarly, the (u, v) th element of the k th power of the adjacency matrix of G gives the number of paths of length k between vertices u and v. Graph powers are implemented in the Wolfram Language as GraphPower[g, k].

adjacency matrix | graph cube | graph square | Pósa's theorem | Seymour conjecture