# Graph power > Mediated Wiki article. Canonical URL: https://mediated.wiki/source/Graph_power > Markdown URL: https://mediated.wiki/source/Graph_power.md > Source: https://en.wikipedia.org/wiki/Graph_power > Source revision: 1335625130 > License: Creative Commons Attribution-ShareAlike 4.0 International (https://creativecommons.org/licenses/by-sa/4.0/) {{short description|Graph of short distances in another graph}} thumb|300px|The square of a graph In [graph theory](/source/graph_theory), a branch of mathematics, the '''{{mvar|k}}th power''' {{mvar|G{{sup|k}}}} of an [undirected graph](/source/undirected_graph) {{mvar|G}} is another graph that has the same set of [vertices](/source/vertex_(graph_theory)), but in which two vertices are adjacent when their [distance](/source/Distance_(graph_theory)) in {{mvar|G}} is at most {{mvar|k}}. Powers of graphs are referred to using terminology similar to that of [exponentiation](/source/exponentiation) of numbers: {{math|''G''{{sup|2}}}} is called the ''[square](/source/Square_number)'' of {{mvar|G}}, {{math|''G''{{sup|3}}}} is called the ''[cube](/source/Cube_(algebra))'' of {{mvar|G}}, etc.{{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}}. Graph powers should be distinguished from the [products](/source/Graph_product) of a graph with itself, which (unlike powers) generally have many more vertices than the original graph. ==Properties== If a graph has [diameter](/source/graph_diameter) {{mvar|d}}, then its {{mvar|d}}-th power is the [complete graph](/source/complete_graph).{{mathworld|id=GraphPower|title=Graph Power|mode=cs2}} If a graph family has bounded [clique-width](/source/clique-width), then so do its {{mvar|d}}-th powers for any fixed {{mvar|d}}.{{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 }}. ===Coloring=== [Graph coloring](/source/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 drawing](/source/graph_drawing)s with high [angular resolution](/source/angular_resolution_(graph_drawing)).{{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](/source/SIAM_Journal_on_Computing) | mr = 1237161 | pages = 1035–1052 | title = Drawing graphs in the plane with high resolution | volume = 22 | year = 1993}}. Both the [chromatic number](/source/chromatic_number) and the [degeneracy](/source/degeneracy_(graph_theory)) of the {{mvar|k}}th power of a [planar graph](/source/planar_graph) of maximum degree {{math|Δ}} are {{math|''O''(Δ{{sup|⌊''k''/2⌋}})}}, where the degeneracy bound shows that a [greedy coloring](/source/greedy_coloring) algorithm may be used to color the graph with this many colors.{{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}}. 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)}}.{{citation | last1 = Kramer | first1 = Florica | last2 = Kramer | first2 = Horst | doi = 10.1016/j.disc.2006.11.059 | issue = 2–3 | journal = [Discrete Mathematics](/source/Discrete_Mathematics_(journal)) | mr = 2378044 | pages = 422–426 | title = A survey on the distance-colouring of graphs | volume = 308 | year = 2008| doi-access = free }}.{{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](/source/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 }}. 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](/source/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|Δ2}} in the worst case, it is smaller for graphs of high [girth](/source/girth_(graph_theory)), being bounded {{math|by ''O''(Δ2 / log Δ)}} in this case.{{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](/source/Combinatorics%2C_Probability_and_Computing) | mr = 1888178 | pages = 1–10 | title = The chromatic number of graph powers | volume = 11 | year = 2002| s2cid = 2706926 }}. Determining the minimum number of colors needed to color the square of a graph is [NP-hard](/source/NP-hard), even in the planar case.{{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). ===Hamiltonicity=== The cube of every connected graph necessarily contains a [Hamiltonian cycle](/source/Hamiltonian_cycle).{{harvtxt|Bondy|Murty|2008}}, p. 105. It is not necessarily the case that the square of a connected graph is Hamiltonian, and it is [NP-complete](/source/NP-complete) to determine whether the square is Hamiltonian.{{citation | last = Underground | first = Polly | authorlink = Václav Chvátal | doi = 10.1016/0012-365X(78)90164-4 | issue = 3 | journal = [Discrete Mathematics](/source/Discrete_Mathematics_(journal)) | mr = 522906 | page = 323 | title = On graphs with Hamiltonian squares | volume = 21 | year = 1978| doi-access = free }}. Nevertheless, by [Fleischner's theorem](/source/Fleischner's_theorem), the square of a [2-vertex-connected graph](/source/k-vertex-connected_graph) is always Hamiltonian.{{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}}. ==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](/source/breadth_first_search) starting from each vertex to determine the distances to all other vertices, or slightly faster using more sophisticated algorithms.{{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 o(mn) time | volume = 8 | year = 2012| s2cid = 1212001 }} Alternatively, If {{mvar|A}} is an [adjacency matrix](/source/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,{{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}}. 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](/source/matrix_multiplication). The {{mvar|k}}th powers of trees can be recognized in time linear in the size of the input graph. {{citation | last1 = Chang | first1 = Maw-Shang | last2 = Ko | first2 = Ming-Tat | last3 = Lu | first3 = Hsueh-I | journal = [Algorithmica](/source/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 }}. Given a graph, deciding whether it is the square of another graph is [NP-complete](/source/NP-complete). {{citation | last1 = Motwani | first1 = R. | last2 = Sudan | first2 = M. | journal = [Discrete Applied Mathematics](/source/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 }}. Moreover, it is [NP-complete](/source/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](/source/bipartite_graph), for {{math|''k'' > 2}}.{{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}}. ==In directed graphs== [[File:Square of digraph.svg|thumb|upright=0.4|The square of a [digraph](/source/directed_graph)]] For the square of [directed graph](/source/directed_graph)s (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](/source/second_neighborhood_problem) can be stated in terms of the square of a digraph, asking if there exists a vertex in every [oriented graph](/source/oriented_graph) whose [degree](/source/degree_(graph_theory)) increase by at least a factor of two when the graph is squared.{{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}} ==Induced subgraphs== [[File:Demi-3-cube.svg|thumb|upright=0.8|{{math|''K''4}} as the half-square of a [cube graph](/source/cube_graph)]] The [half-square](/source/half-square) of a [bipartite graph](/source/bipartite_graph) {{mvar|G}} is the subgraph of {{math|''G''2}} induced by one side of the bipartition of {{mvar|G}}. [Map graph](/source/Map_graph)s are the half-squares of [planar graph](/source/planar_graph)s,{{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](/source/Journal_of_the_ACM) | mr = 2147819 | pages = 127–138 | title = Map graphs | volume = 49 | year = 2002| arxiv = cs/9910013| s2cid = 2657838 }}. and [halved cube graph](/source/halved_cube_graph)s are the half-squares of [hypercube graph](/source/hypercube_graph)s.{{citation | last = Shpectorov | first = S. V. | doi = 10.1006/eujc.1993.1016 | issue = 2 | journal = [European Journal of Combinatorics](/source/European_Journal_of_Combinatorics) | mr = 1206617 | pages = 117–130 | title = On scale embeddings of graphs into hypercubes | volume = 14 | year = 1993| doi-access = free }}. [Leaf power](/source/Leaf_power)s 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}}.{{citation | last1 = Nishimura | first1 = N. | last2 = Ragde | first2 = P. | last3 = Thilikos | first3 = D.M. | journal = [Journal of Algorithms](/source/Journal_of_Algorithms) | pages = 69–108 | title = On graph powers for leaf-labeled trees | volume = 42 | year = 2002 | doi=10.1006/jagm.2001.1195}}. ==References== {{reflist}} Category:Graph operations --- Adapted from the Wikipedia article [Graph power](https://en.wikipedia.org/wiki/Graph_power) by Wikipedia contributors ([contributor history](https://en.wikipedia.org/wiki/Graph_power?action=history)). Available under [Creative Commons Attribution-ShareAlike 4.0 International](https://creativecommons.org/licenses/by-sa/4.0/). Changes may have been made.