Graph power

Content sourced from Wikipedia, licensed under CC BY-SA 3.0.

The kth power of a graph G is a new graph with the same vertices, where two vertices are connected if their distance in G is at most k. The case k=2 is called the square of G, k=3 the cube, and so on. Powers keep the same vertex set, unlike multiplying graphs with themselves, which usually creates more vertices.

Key ideas and facts
- If G has diameter d, then its d-th power G^d is a complete graph (everyone is connected to everyone).
- If a graph family has bounded clique-width, then so do its d-th powers for any fixed d.
- Coloring the square G^2 can help assign frequencies in wireless networks to avoid interference, and it can help create drawings with good angular resolution.

Planar graphs and bounds
- For a planar graph with maximum degree Δ, both the chromatic number and the degeneracy of G^k are O(Δ ⌊k/2⌋). In particular, the square G^2 is colorable with a number of colors that grows roughly with Δ.
- For squares (k=2), there is a famous conjecture (Wegner) that χ(G^2) ≤ max(Δ+5, 3Δ/2+1). The best general bound known is χ(G^2) ≤ 5Δ/3 + O(1).
- In general, if a graph has degeneracy d and maximum degree Δ, then the degeneracy of G^2 is O(dΔ). So many sparse graphs have squares whose chromatic number is proportional to Δ.
- For nonplanar graphs, χ(G^2) can be as large as about Δ^2 in the worst case, but graphs with high girth satisfy χ(G^2) = O(Δ^2 / log Δ).
- Deciding the minimum number of colors needed to color G^2 is NP-hard, even for planar graphs.

Hamiltonicity and related results
- The cube G^3 of every connected graph always contains a Hamiltonian cycle.
- The square G^2 of a connected graph need not be Hamiltonian.
- Fleischner’s theorem says the square of any 2-vertex-connected graph is Hamiltonian.

Computing kth powers
- A simple method: run BFS from each vertex to compute distances to all others; this gives G^k in time O(mn). There are faster approaches with advanced algorithms.
- If you use the adjacency matrix A and modify it to have nonzero diagonal entries, then the nonzero entries of A^k reveal the edges of G^k. This links computing powers to fast matrix multiplication.
- Powers of trees can be recognized in linear time.
- In general, deciding if a graph is the square (or a kth power) of another graph is NP-complete.

Directed graphs (digraphs)
- For a digraph, the square connects pairs of vertices that have a directed path of length two in the same direction. If two vertices both point to the same vertex, that does not create a connection between them.

Other concepts and related ideas
- The second neighborhood problem asks about growth when squaring a digraph.
- The half-square of a bipartite graph G is the subgraph of G^2 induced by one side of the bipartition.
- Map graphs are half-squares of planar graphs; halved cube graphs are half-squares of hypercubes.
- Leaf powers are subgraphs induced by the leaves of a tree from the tree’s powers; a k-leaf power uses exponent k.

In short, graph powers expand connections based on distance, with many implications for coloring, connectivity, and algorithms. They have a rich set of theoretical results and practical applications across various graph families and problem types.