{{short description|Graph of short distances in another graph}} thumb|300px|The square of a graph

In graph theory, a branch of mathematics, the '''{{mvar|k}}th power''' {{mvar|G{{sup|k}}}} of an undirected graph {{mvar|G}} is another graph that has the same set of vertices, but in which two vertices are adjacent when their distance in {{mvar|G}} is at most&nbsp;{{mvar|k}}. Powers of graphs are referred to using terminology similar to that of exponentiation of numbers: {{math|''G''{{sup|2}}}} is called the ''square'' of {{mvar|G}}, {{math|''G''{{sup|3}}}} is called the ''cube'' of {{mvar|G}}, etc.<ref>{{citation|title=Graph Theory|volume=244|series=Graduate Texts in Mathematics|first1=Adrian|last1=Bondy|first2=U. S. R.|last2=Murty|publisher=Springer|year=2008|isbn=9781846289699|page=82|url=https://books.google.com/books?id=HuDFMwZOwcsC&pg=PA82}}.</ref>

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 {{mvar|d}}, then its {{mvar|d}}-th power is the complete graph.<ref>{{mathworld|id=GraphPower|title=Graph Power|mode=cs2}}</ref> If a graph family has bounded clique-width, then so do its {{mvar|d}}-th powers for any fixed {{mvar|d}}.<ref>{{citation | last = Todinca | first = Ioan | contribution = Coloring powers of graphs of bounded clique-width | doi = 10.1007/978-3-540-39890-5_32 | mr = 2080095 | pages = 370–382 | publisher = Springer, Berlin | series = Lecture Notes in Comput. Sci. | title = Graph-theoretic concepts in computer science | volume = 2880 | year = 2003 | isbn = 978-3-540-20452-7 }}.</ref>

===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,<ref name="ah00"/> and to find graph drawings with high angular resolution.<ref>{{citation | last1 = Formann | first1 = M. | last2 = Hagerup | first2 = T. | last3 = Haralambides | first3 = J. | last4 = Kaufmann | first4 = M. | last5 = Leighton | first5 = F. T. | author5-link = F. Thomson Leighton | last6 = Symvonis | first6 = A. | last7 = Welzl | first7 = E. | author7-link = Emo Welzl | last8 = Woeginger | first8 = G. | author8-link = Gerhard J. Woeginger | doi = 10.1137/0222063 | issue = 5 | journal = SIAM Journal on Computing | mr = 1237161 | pages = 1035–1052 | title = Drawing graphs in the plane with high resolution | volume = 22 | year = 1993}}.</ref>

Both the chromatic number and the degeneracy of the {{mvar|k}}th power of a planar graph of maximum degree {{math|Δ}} are {{math|''O''(Δ{{sup|⌊''k''/2⌋}})}}, where the degeneracy bound shows that a greedy coloring algorithm may be used to color the graph with this many colors.<ref name="ah00">{{citation | last1 = Agnarsson | first1 = Geir | last2 = Halldórsson | first2 = Magnús M. | contribution = Coloring powers of planar graphs | location = San Francisco, California, USA | pages = 654–662 | title = Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '00) | year = 2000}}.</ref> 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 {{math|max(Δ + 5, {{sfrac|3Δ|2}} + 1)}}, and it is known that the chromatic number is at most {{math|{{sfrac|5Δ|3}} + ''O''(1)}}.<ref>{{citation | last1 = Kramer | first1 = Florica | last2 = Kramer | first2 = Horst | doi = 10.1016/j.disc.2006.11.059 | issue = 2–3 | journal = Discrete Mathematics | mr = 2378044 | pages = 422–426 | title = A survey on the distance-colouring of graphs | volume = 308 | year = 2008| doi-access = free }}.</ref><ref>{{citation | last1 = Molloy | first1 = Michael | last2 = Salavatipour | first2 = Mohammad R. | doi = 10.1016/j.jctb.2004.12.005 | issue = 2 | journal = Journal of Combinatorial Theory | series = Series B | mr = 2145512 | pages = 189–213 | title = A bound on the chromatic number of the square of a planar graph | volume = 94 | year = 2005| hdl = 1807/9473 | hdl-access = free }}.</ref> More generally, for any graph with degeneracy {{mvar|d}} and maximum degree {{math|Δ}}, the degeneracy of the square of the graph is {{math|''O''({{mvar|d}}Δ)}}, so many types of sparse graph other than the planar graphs also have squares whose chromatic number is proportional to {{math|Δ}}.

Although the chromatic number of the square of a nonplanar graph with maximum degree {{math|Δ}} may be proportional to {{math|Δ<sup>2</sup>}} in the worst case, it is smaller for graphs of high girth, being bounded {{math|by ''O''(Δ<sup>2</sup> / log Δ)}} in this case.<ref>{{citation | last1 = Alon | first1 = Noga | author1-link = Noga Alon | last2 = Mohar | first2 = Bojan | author2-link = Bojan Mohar | doi = 10.1017/S0963548301004965 | issue = 1 | journal = Combinatorics, Probability and Computing | mr = 1888178 | pages = 1–10 | title = The chromatic number of graph powers | volume = 11 | year = 2002| s2cid = 2706926 }}.</ref>

Determining the minimum number of colors needed to color the square of a graph is NP-hard, even in the planar case.<ref>{{harvtxt|Agnarsson|Halldórsson|2000}} list publications proving NP-hardness for general graphs by McCormick (1983) and Lin and Skiena (1995), and for planar graphs by Ramanathan and Lloyd (1992, 1993).</ref>

===Hamiltonicity=== The cube of every connected graph necessarily contains a Hamiltonian cycle.<ref>{{harvtxt|Bondy|Murty|2008}}, p. 105.</ref> 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.<ref>{{citation | last = Underground | first = Polly | authorlink = Václav Chvátal | doi = 10.1016/0012-365X(78)90164-4 | issue = 3 | journal = Discrete Mathematics | mr = 522906 | page = 323 | title = On graphs with Hamiltonian squares | volume = 21 | year = 1978| doi-access = free }}.</ref> Nevertheless, by Fleischner's theorem, the square of a 2-vertex-connected graph is always Hamiltonian.<ref>{{citation | last = Diestel | first = Reinhard | contribution = 10. Hamiltonian cycles | edition = corrected 4th electronic | title = Graph Theory | url = https://www.math.uni-hamburg.de/home/diestel/books/graph.theory/preview/Ch10.pdf | year = 2012}}.</ref>

==Computational complexity== The {{mvar|k}}th power of a graph with {{mvar|n}} vertices and {{mvar|m}} edges may be computed in time {{math|''O''(''mn'')}} 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.<ref>{{citation | last = Chan | first = Timothy M. | doi = 10.1145/2344422.2344424 | issue = 4 | journal = ACM Transactions on Algorithms | mr = 2981912 | pages = A34:1–A34:17 | title = All-pairs shortest paths for unweighted undirected graphs in <math>o(mn)</math> time | volume = 8 | year = 2012| s2cid = 1212001 }}</ref> Alternatively, If {{mvar|A}} is an adjacency matrix for the graph, modified to have nonzero entries on its main diagonal, then the nonzero entries of {{mvar|A{{sup|k}}}} give the adjacency matrix of the {{mvar|k}}th power of the graph,<ref>{{citation|title=Handbook of Product Graphs|edition=2nd|series=Discrete Mathematics and Its Applications|first1=Richard|last1=Hammack|first2=Wilfried|last2=Imrich|first3=Sandi|last3=Klavžar|author3-link=Sandi Klavžar|publisher=CRC Press|year=2011|isbn=9781439813058|page=94|url=https://books.google.com/books?id=WiB6UO1nqHAC&pg=PA94}}.</ref> from which it follows that constructing {{mvar|k}}th powers may be performed in an amount of time that is within a logarithmic factor of the time for matrix multiplication.

The {{mvar|k}}th powers of trees can be recognized in time linear in the size of the input graph. <ref>{{citation | last1 = Chang | first1 = Maw-Shang | last2 = Ko | first2 = Ming-Tat | last3 = Lu | first3 = Hsueh-I | journal = Algorithmica | title = Linear-Time Algorithms for Tree Root Problems | pages = 471–495 | year = 2015 | volume = 71 | number = 2 | doi=10.1007/s00453-013-9815-y| s2cid = 253971732 }}.</ref>

Given a graph, deciding whether it is the square of another graph is NP-complete. <ref>{{citation | last1 = Motwani | first1 = R. | last2 = Sudan | first2 = M. | journal = Discrete Applied Mathematics | pages = 81–88 | title = Computing roots of graphs is hard | volume = 54 | year = 1994 | doi=10.1016/0166-218x(94)00023-9| doi-access = free }}.</ref> Moreover, it is NP-complete to determine whether a graph is a {{mvar|k}}th power of another graph, for a given number {{math|''k'' ≥ 2}}, or whether it is a {{mvar|k}}th power of a bipartite graph, for {{math|''k'' > 2}}.<ref>{{citation | last1 = Le | first1 = Van Bang | last2 = Nguyen | first2 = Ngoc Tuy | contribution = Hardness results and efficient algorithms for graph powers | doi = 10.1007/978-3-642-11409-0_21 | location = Berlin | mr = 2587715 | pages = 238–249 | publisher = Springer | series = Lecture Notes in Computer Science | title = Graph-Theoretic Concepts in Computer Science: 35th International Workshop, WG 2009, Montpellier, France, June 24-26, 2009, Revised Papers | volume = 5911 | year = 2010 | isbn = 978-3-642-11408-3}}.</ref>

==In directed graphs== [[File:Square of digraph.svg|thumb|upright=0.4|The square of a digraph]] For the square of directed graphs (or digraphs), each pair of vertices connected by a directed path of length two become connected by a path in the same direction of length one. Pairs of points directed to the same vertex, then, do not cause a connection between them in the square of a directed graph.

The second neighborhood problem can be stated in terms of the square of a digraph, asking if there exists a vertex in every oriented graph whose degree increase by at least a factor of two when the graph is squared.<ref name=dl95>{{citation | last1 = Dean | first1 = Nathaniel | last2 = Latka | first2 = Brenda J. | department = Proceedings of the Twenty-Sixth Southeastern International Conference on Combinatorics, Graph Theory and Computing (Boca Raton, FL, 1995) | journal = Congressus Numerantium | mr = 1369296 | pages = 73–80 | title = Squaring the tournament—an open problem | volume = 109 | year = 1995}}</ref>

==Induced subgraphs== [[File:Demi-3-cube.svg|thumb|upright=0.8|{{math|''K''<sub>4</sub>}} as the half-square of a cube graph]] The half-square of a bipartite graph {{mvar|G}} is the subgraph of {{math|''G''<sup>2</sup>}} induced by one side of the bipartition of {{mvar|G}}. Map graphs are the half-squares of planar graphs,<ref>{{citation | last1 = Chen | first1 = Zhi-Zhong | last2 = Grigni | first2 = Michelangelo | last3 = Papadimitriou | first3 = Christos H. | author3-link = Christos Papadimitriou | doi = 10.1145/506147.506148 | issue = 2 | journal = Journal of the ACM | mr = 2147819 | pages = 127–138 | title = Map graphs | volume = 49 | year = 2002| arxiv = cs/9910013| s2cid = 2657838 }}.</ref> and halved cube graphs are the half-squares of hypercube graphs.<ref>{{citation | last = Shpectorov | first = S. V. | doi = 10.1006/eujc.1993.1016 | issue = 2 | journal = European Journal of Combinatorics | mr = 1206617 | pages = 117–130 | title = On scale embeddings of graphs into hypercubes | volume = 14 | year = 1993| doi-access = free }}.</ref>

Leaf powers are the subgraphs of powers of trees induced by the leaves of the tree. A {{mvar|k}}-leaf power is a leaf power whose exponent is {{mvar|k}}.<ref>{{citation | last1 = Nishimura | first1 = N. | last2 = Ragde | first2 = P. | last3 = Thilikos | first3 = D.M. | journal = Journal of Algorithms | pages = 69–108 | title = On graph powers for leaf-labeled trees | volume = 42 | year = 2002 | doi=10.1006/jagm.2001.1195}}.</ref>

==References== {{reflist}}

Category:Graph operations