“Graph power”的意思、由来-开放百科全书

In graph theory, a branch of mathematics, the kth power G^k of an undirected graph G is another graph that has the same set of vertices, but in which two vertices are adjacent when their distance in G is at most k. Powers of graphs are referred to using terminology similar to that of exponentiation of numbers: G² is called the square of G, G³ is called the cube of G, etc.^[1]

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 d, then its d-th power is the complete graph.^[2] If a graph family has bounded clique-width, then so do its d-th powers for any fixed d.^[3]

Coloring

Both the chromatic number and the degeneracy of the kth power of a planar graph of maximum degree Δ are

, where the degeneracy bound shows that a greedy coloring algorithm may be used to color the graph with this many colors.^[5] 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

.^[6]^[7] More generally, for any graph with degeneracy d and maximum degree Δ, the degeneracy of the square of the graph is O(dΔ), so many types of sparse graph 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, being bounded by O(Δ²/log Δ) in this case.^[8]

Determining the minimum number of colors needed to color the square of a graph is NP-hard, even in the planar case.^[9]

Hamiltonicity

The cube of every connected graph necessarily contains a Hamiltonian cycle.^[10] 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.^[11] Nevertheless, by Fleischner's theorem, the square of a 2-vertex-connected graph is always Hamiltonian.^[12]

Computational complexity

The kth 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^k give the adjacency matrix of the kth power of the graph,^[13] from which it follows that constructing kth powers may be performed in an amount of time that is within a logarithmic factor of the time for matrix multiplication.

The kth 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 kth power of another graph, for a given number k ≥ 2, or whether it is a kth power of a bipartite graph, for k > 2.^[16]

Induced subgraphs

The half-square of a bipartite graph {{mvar|G}} is the subgraph of {{math|G²}} induced by one side of the bipartition of {{mvar|G}}. Map graphs are the half-squares of planar graphs,^[17] and halved cube graphs are the half-squares of hypercube graphs.^[18]

References

1. ^{{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}}.
2. ^{{mathworld|id=GraphPower|title=Graph Power}}
3. ^{{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}}.
4. ^{{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}}.
5. ^¹{{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}}.
6. ^{{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}}.
7. ^{{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}}.
8. ^{{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}}.
9. ^{{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).
10. ^{{harvtxt|Bondy|Murty|2008}}, p. 105.
11. ^{{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}}.
12. ^{{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}}.
13. ^{{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}}.
14. ^{{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}}.
15. ^{{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}}.
16. ^{{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}}.
17. ^{{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}}.
18. ^{{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}}.
19. ^{{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}}.