Graph power

The square of a graph

In graph theory, a branch of mathematics, the Template:Mvarth power Template:Mvar of an undirected graph Template:Mvar is another graph that has the same set of vertices, but in which two vertices are adjacent when their distance in Template:Mvar is at most Template:Mvar. Powers of graphs are referred to using terminology similar to that of exponentiation of numbers: Template:Math is called the square of Template:Mvar, Template:Math is called the cube of Template:Mvar, 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.

Properties

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

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 Template:Mvarth power of a planar graph of maximum degree Template:Math are Template:Math, 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 Template:Math, and it is known that the chromatic number is at most Template:Math. More generally, for any graph with degeneracy Template:Mvar and maximum degree Template:Math, the degeneracy of the square of the graph is Template:Math, so many types of sparse graph other than the planar graphs also have squares whose chromatic number is proportional to Template:Math.

Although the chromatic number of the square of a nonplanar graph with maximum degree Template:Math may be proportional to Template:Math in the worst case, it is smaller for graphs of high girth, being bounded Template:Math 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 Template:Mvarth power of a graph with Template:Mvar vertices and Template:Mvar edges may be computed in time Template:Math by performing a breadth first search starting from each vertex to determine the distances to all other vertices, or slightly faster using more sophisticated algorithms. Alternatively, If Template:Mvar is an adjacency matrix for the graph, modified to have nonzero entries on its main diagonal, then the nonzero entries of Template:Mvar give the adjacency matrix of the Template:Mvarth power of the graph, from which it follows that constructing Template:Mvarth powers may be performed in an amount of time that is within a logarithmic factor of the time for matrix multiplication.

The Template:Mvarth powers of trees can be recognized in time linear in the size of the input graph.

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 Template:Mvarth power of another graph, for a given number Template:Math, or whether it is a Template:Mvarth power of a bipartite graph, for Template:Math.

Induced subgraphs

Template:Math as the half-square of a cube graph

The half-square of a bipartite graph Template:Mvar is the subgraph of Template:Math induced by one side of the bipartition of Template:Mvar. 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 Template:Mvar-leaf power is a leaf power whose exponent is Template:Mvar.