 | ||
In graph theory, a branch of mathematics, the kth power Gk 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: G2 is called the square of G, G3 is called the cube of G, etc.
Contents
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.
Properties
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.
Coloring
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
Although the chromatic number of the square of a nonplanar graph with maximum degree Δ may be proportional to Δ2 in the worst case, it is smaller for graphs of high girth, being bounded by O(Δ2/log Δ) in this case.
Determining the minimum number of colors needed to color the square of a graph is NP-hard, even in the planar case.
Hamiltonicity
The cube of every connected graph necessarily contains a Hamiltonian cycle. It is not necessarily the case that the square of a connected graph is Hamiltonian, and it is NP-complete to determine whether the square is Hamiltonian. Nevertheless, by Fleischner's theorem, the square of a 2-vertex-connected graph is always Hamiltonian.
Computational complexity
The kth power of a graph with n vertices and m edges may be computed in time O(mn) by performing a breadth first search starting from each vertex to determine the distances to all other vertices. Alternatively, If A is an adjacency matrix for the graph, modified to have nonzero entries on its main diagonal, then the nonzero entries of Ak give the adjacency matrix of the kth power of the graph, from which it follows that constructing kth powers may be performed in an amount of time that is within a logarithmic factor of the time for matrix multiplication.
Given a graph, deciding whether it is the square of another graph is NP-complete. Moreover, it is NP-complete to determine whether a graph is a kth power of another graph, for a given number k ≥ 2, or whether it is a kth power of a bipartite graph, for k > 2.
Induced subgraphs
The half-square of a bipartite graph G is the subgraph of G2 induced by one side of the bipartition of G. Map graphs are the half-squares of planar graphs, and halved cube graphs are the half-squares of hypercube graphs.
Leaf powers are the subgraphs of powers of trees induced by the leaves of the tree. A k-leaf power is a leaf power whose exponent is k.