View source for RRNA small subunit pseudouridine methyltransferase Nep1

[[File:Square of a graph.svg|thumb|300px|The square of a graph]]
In [[graph theory]], a branch of mathematics, the '''''k''th power''' ''G''<sup>''k''</sup> of an undirected graph ''G'' is another graph that has the same set of [[vertex (graph theory)|vertices]], but in which two vertices are adjacent when their [[Distance (graph theory)|distance]] in ''G'' is at most&nbsp;''k''. Powers of graphs are referred to using terminology similar to that for [[exponentiation]] of numbers: ''G''<sup>2</sup> is called the '''square''' of ''G'', ''G''<sup>3</sup> is called the '''cube''' of ''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=http://books.google.com/books?id=HuDFMwZOwcsC&pg=PA82}}.</ref>

Graph powers should be distinguished from the [[Graph product|products]] of a graph with itself, which (unlike powers) generally have many more vertices than the original graph.

==Properties==
If a graph has [[graph diameter|diameter]] ''d'', then its ''d''-th power is the [[complete graph]].<ref>{{mathworld|id=GraphPower|title=Graph Power}}</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 drawing]]s with high [[angular resolution (graph drawing)|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.
 | 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 (graph theory)|degeneracy]] of the ''k''th power of a [[planar graph]] of maximum degree &Delta; are <math>O(\Delta^{\lfloor k/2\rfloor})</math>, 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\left(d+5, \frac{3d}{2}+1\right)</math>, and it is known that the chromatic number is at most <math>\frac{5d}{3}+O(1)</math>.<ref>{{citation
 | last1 = Kramer | first1 = Florica
 | last2 = Kramer | first2 = Horst
 | doi = 10.1016/j.disc.2006.11.059
 | issue = 2-3
 | journal = [[Discrete Mathematics (journal)|Discrete Mathematics]]
 | mr = 2378044
 | pages = 422–426
 | title = A survey on the distance-colouring of graphs
 | volume = 308
 | year = 2008}}.</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}}.</ref> More generally, for any graph with degeneracy ''d'' and maximum degree &Delta;, the degeneracy of the square of the graph is ''O''(''d''&Delta;), so many types of [[sparse graph]] other than the planar graphs also have squares whose chromatic number is proportional to &Delta;.

Although the chromatic number of the square of a nonplanar graph with maximum degree &Delta; may be proportional to &Delta;<sup>2</sup> in the worst case, it is smaller for graphs of high [[girth (graph theory)|girth]], being bounded by O(&Delta;<sup>2</sup>/log&nbsp;&Delta;) 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}}.</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}} 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 = Paris
 | doi = 10.1016/0012-365X(78)90164-4
 | issue = 3
 | journal = [[Discrete Mathematics (journal)|Discrete Mathematics]]
 | mr = 522906
 | page = 323
 | title = On graphs with Hamiltonian squares
 | volume = 21
 | year = 1978}}.</ref> Nevertheless, by [[Fleischner's theorem]], the square of a [[k-vertex-connected graph|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 = http://www.math.uni-hamburg.de/home/diestel/books/graph.theory/preview/Ch10.pdf
 | year = 2012}}.</ref>

==Computational complexity==
The ''k''th 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 ''A''<sup>''k''</sup> give the adjacency matrix of the ''k''th power of the graph, from which it follows that constructing ''k''th powers may be performed in an amount of time that is within a logarithmic factor of the time for [[matrix multiplication]].

The [[induced subgraph]] of the ''k''th power of a [[tree (graph theory)|tree]], induced by the leaves of the tree, may be recognized in [[polynomial time]]; this problem has applications in [[phylogeny]].<ref>{{citation
 | last1 = Nishimura | first1 = Naomi
 | last2 = Ragde | first2 = Prabhakar
 | last3 = Thilikos | first3 = Dimitrios M.
 | doi = 10.1006/jagm.2001.1195
 | issue = 1
 | journal = Journal of Algorithms
 | mr = 1874637
 | pages = 69–108
 | title = On graph powers for leaf-labeled trees
 | volume = 42
 | year = 2002}}.</ref>

It is [[NP-complete]] to determine whether a graph is a ''k''th power of another graph, for a given number ''k''&nbsp;≥&nbsp;2, or whether it is a ''k''th power of a [[bipartite graph]], for ''k''&nbsp;>&nbsp;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>

==References==
{{reflist}}

[[Category:Graph operations]]