The kth 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 kth 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