Graph power

In graph theory, a branch of mathematics, the kth power G^k of an undirected graph G 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 for 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.

If a graph has diameter d, then its d-th power is the complete graph. If a graph family has bounded clique-width, then so do its d-th powers for any fixed d.

Graph coloring on the square of a graph may be used to assign frequencies to the participants of wireless communication networks so that no two participants interfere with each other at any of their common neighbors, and to find graph drawings with high angular resolution.

Both the chromatic number and the degeneracy of the kth power of a planar graph of maximum degree Δ are ${\displaystyle O(\Delta ^{\lfloor k/2\rfloor })}$, where the degeneracy bound shows that a greedy coloring algorithm may be used to color the graph with this many colors. For the special case of a square of a planar graph, Wegner conjectured in 1977 that the chromatic number of the square of a planar graph is at most ${\displaystyle \max \left(d+5,{\frac {3d}{2}}+1\right)}$, and it is known that the chromatic number is at most ${\displaystyle {\frac {5d}{3}}+O(1)}$. More generally, for any graph with degeneracy d and maximum degree Δ, the degeneracy of the square of the graph is O(dΔ), so many types of sparse graph other than the planar graphs also have squares whose chromatic number is proportional to Δ.

...
Wikipedia