Graph power

In graph theory, a branch of mathematics, the kth powerG of an undirected graphG is another graph that has the same set of vertices, but in which two vertices are adjacent when their distance in G is at most k. Powers of graphs are referred to using terminology similar to that of exponentiation of numbers: G is called the square of G, G is called the cube of G, etc.

Graph powers should be distinguished from the products of a graph with itself, which (unlike powers) generally have many more vertices than the original graph.