graph theory In mathematics, graph theory is the study of ''graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conne ...

, a branch of mathematics, the th power of an

undirected graph In discrete mathematics, and more specifically in graph theory, a graph is a structure amounting to a set of objects in which some pairs of the objects are in some sense "related". The objects correspond to mathematical abstractions called '' v ...

is another graph that has the same set of vertices, but in which two vertices are adjacent when their

distance Distance is a numerical or occasionally qualitative measurement of how far apart objects or points are. In physics or everyday usage, distance may refer to a physical length or an estimation based on other criteria (e.g. "two counties over"). ...

in is at most . Powers of graphs are referred to using terminology similar to that of

exponentiation Exponentiation is a mathematical operation, written as , involving two numbers, the '' base'' and the ''exponent'' or ''power'' , and pronounced as " (raised) to the (power of) ". When is a positive integer, exponentiation corresponds to re ...

of numbers: is called the ''

square In Euclidean geometry, a square is a regular quadrilateral, which means that it has four equal sides and four equal angles (90-degree angles, π/2 radian angles, or right angles). It can also be defined as a rectangle with two equal-length adj ...

'' of , is called the ''

cube In geometry, a cube is a three-dimensional solid object bounded by six square faces, facets or sides, with three meeting at each vertex. Viewed from a corner it is a hexagon and its net is usually depicted as a cross. The cube is the only r ...

'' of , etc. Graph powers should be distinguished from the

products Product may refer to: Business * Product (business), an item that serves as a solution to a specific consumer problem. * Product (project management), a deliverable or set of deliverables that contribute to a business solution Mathematics * Produ ...

of a graph with itself, which (unlike powers) generally have many more vertices than the original graph.

Properties

If a graph has

diameter In geometry, a diameter of a circle is any straight line segment that passes through the center of the circle and whose endpoints lie on the circle. It can also be defined as the longest chord of the circle. Both definitions are also valid for ...

, then its -th power is the

complete graph In the mathematical field of graph theory, a complete graph is a simple undirected graph in which every pair of distinct vertices is connected by a unique edge. A complete digraph is a directed graph in which every pair of distinct vertices is c ...

. If a graph family has bounded

clique-width In graph theory, the clique-width of a graph is a parameter that describes the structural complexity of the graph; it is closely related to treewidth, but unlike treewidth it can be bounded even for dense graphs. It is defined as the minimum num ...

, then so do its -th powers for any fixed .

Coloring

Graph coloring In graph theory, graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called "colors" to elements of a graph subject to certain constraints. In its simplest form, it is a way of coloring the vertices o ...

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 drawing Graph drawing is an area of mathematics and computer science combining methods from geometric graph theory and information visualization to derive two-dimensional depictions of graph (discrete mathematics), graphs arising from applications such a ...

s with high

angular resolution Angular resolution describes the ability of any image-forming device such as an optical or radio telescope, a microscope, a camera, or an eye, to distinguish small details of an object, thereby making it a major determinant of image resolution. ...

. Both the

chromatic number In graph theory, graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called "colors" to elements of a graph subject to certain constraints. In its simplest form, it is a way of coloring the vertices o ...

and the

degeneracy Degeneracy, degenerate, or degeneration may refer to: Arts and entertainment * ''Degenerate'' (album), a 2010 album by the British band Trigger the Bloodshed * Degenerate art, a term adopted in the 1920s by the Nazi Party in Germany to descri ...

of the th power of a

planar graph In graph theory, a planar graph is a graph that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints. In other words, it can be drawn in such a way that no edges cross ...

of maximum degree are , where the degeneracy bound shows that a

greedy coloring In the study of graph coloring problems in mathematics and computer science, a greedy coloring or sequential coloring is a coloring of the vertices of a graph formed by a greedy algorithm that considers the vertices of the graph in sequence an ...

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 , and it is known that the chromatic number is at most . More generally, for any graph with degeneracy and maximum degree , the degeneracy of the square of the graph is , so many types of

sparse graph In mathematics, a dense graph is a graph in which the number of edges is close to the maximal number of edges (where every pair of vertices is connected by one edge). The opposite, a graph with only a few edges, is a sparse graph. The distinction ...

other than the planar graphs also have squares whose chromatic number is proportional to . Although the chromatic number of the square of a nonplanar graph with maximum degree may be proportional to in the worst case, it is smaller for graphs of high

girth Girth may refer to: ;Mathematics * Girth (functional analysis), the length of the shortest centrally symmetric simple closed curve on the unit sphere of a Banach space * Girth (geometry), the perimeter of a parallel projection of a shape * Girth ...

, being bounded in this case. Determining the minimum number of colors needed to color the square of a graph is

NP-hard In computational complexity theory, NP-hardness ( non-deterministic polynomial-time hardness) is the defining property of a class of problems that are informally "at least as hard as the hardest problems in NP". A simple example of an NP-hard pr ...

, even in the planar case.

Hamiltonicity

The cube of every connected graph necessarily contains a

Hamiltonian cycle In the mathematical field of graph theory, a Hamiltonian path (or traceable path) is a path in an undirected or directed graph that visits each vertex exactly once. A Hamiltonian cycle (or Hamiltonian circuit) is a cycle that visits each vertex ...

. It is not necessarily the case that the square of a connected graph is Hamiltonian, and it is

NP-complete In computational complexity theory, a problem is NP-complete when: # it is a problem for which the correctness of each solution can be verified quickly (namely, in polynomial time) and a brute-force search algorithm can find a solution by tryi ...

to determine whether the square is Hamiltonian. Nevertheless, by

Fleischner's theorem In graph theory, a branch of mathematics, Fleischner's theorem gives a sufficient condition for a graph to contain a Hamiltonian cycle. It states that, if is a 2-vertex-connected graph, then the square of is Hamiltonian. it is named after He ...

, the square of a 2-vertex-connected graph is always Hamiltonian.

Computational complexity

The th power of a graph with vertices and edges may be computed in time by performing a

breadth first search Breadth-first search (BFS) is an algorithm for searching a tree data structure for a node that satisfies a given property. It starts at the tree root and explores all nodes at the present depth prior to moving on to the nodes at the next de ...

starting from each vertex to determine the distances to all other vertices, or slightly faster using more sophisticated algorithms. Alternatively, If is an

adjacency matrix In graph theory and computer science, an adjacency matrix is a square matrix used to represent a finite graph. The elements of the matrix indicate whether pairs of vertices are adjacent or not in the graph. In the special case of a finite simp ...

for the graph, modified to have nonzero entries on its main diagonal, then the nonzero entries of give the adjacency matrix of the th power of the graph, from which it follows that constructing th powers may be performed in an amount of time that is within a logarithmic factor of the time for

matrix multiplication In mathematics, particularly in linear algebra, matrix multiplication is a binary operation that produces a matrix from two matrices. For matrix multiplication, the number of columns in the first matrix must be equal to the number of rows in the s ...

. The th 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

. Moreover, it is

to determine whether a graph is a th power of another graph, for a given number , or whether it is a th power of a

bipartite graph In the mathematical field of graph theory, a bipartite graph (or bigraph) is a graph whose vertices can be divided into two disjoint and independent sets U and V, that is every edge connects a vertex in U to one in V. Vertex sets U and V are ...

, for .

Induced subgraphs

The

half-square In graph theory, the bipartite half or half-square of a bipartite graph is a graph whose vertex set is one of the two sides of the bipartition (without loss of generality, ) and in which there is an edge for each pair of vertices in that ar ...

of a

is the subgraph of induced by one side of the bipartition of .

Map graph In graph theory, a branch of mathematics, a map graph is an undirected graph formed as the intersection graph of finitely many simply connected and internally disjoint regions of the Euclidean plane. The map graphs include the planar graphs, b ...

s are the half-squares of

s, and

halved cube graph In graph theory, the halved cube graph or half cube graph of dimension is the graph of the demihypercube, formed by connecting pairs of vertices at distance exactly two from each other in the hypercube graph. That is, it is the half-square o ...

s are the half-squares of

hypercube graph In graph theory, the hypercube graph is the graph formed from the vertices and edges of an -dimensional hypercube. For instance, the cube graph is the graph formed by the 8 vertices and 12 edges of a three-dimensional cube. has vertices, ...

Leaf power In the mathematical area of graph theory, a -leaf power of a tree is a graph whose vertices are the leaves of and whose edges connect pairs of leaves whose distance in is at most . That is, is an induced subgraph of the graph power , induce ...

s are the subgraphs of powers of trees induced by the leaves of the tree. A -leaf power is a leaf power whose exponent is ..

References

{{reflist Graph operations