圖的次冪

在數學的一個分支圖論中，一個無向圖的k次冪G^k指的是另一個有相同頂點集的圖，但在G中所有距離小於k的頂點在該圖中是相鄰的。圖的次冪常用數的次冪相關術語來表示：G²被稱為G的平方，G³被稱為立方，以此類推。^[1]

圖的次冪應該與圖本身的乘積區別開來，圖的乘積（與次冪不同）通常比原圖有更多的頂點。

屬性

如果一個圖的直徑是d，那麼它的d次冪就是完全圖。^[2]如果一個圖族具有有界的團寬，那麼對於任意固定的d，它的d次冪也具有有界的團寬。^[3]

着色

圖平方的着色可以用來為無線通信網絡的參與者分配頻率，使兩個參與者互動時不受任何共同鄰居的干擾，並可以在圖繪製時找到角解像度高的圖。^[4]^[5]

最大度為Δ的平面圖的k次冪其着色數和簡併度均為 $O(\Delta ^{\lfloor k/2\rfloor })$ ，其中簡併度表明顏色貪婪算法可利用這麼多顏色給圖着色。^[4] 考慮一個平面圖平方的特例，Wegner在1977年推算出平面圖平方的最大着色數為 $\max \left(\Delta +5,{\frac {3\Delta }{2}}+1\right)$ 而目前更普遍的最大着色數為 ${\frac {5\Delta }{3}}+O(1)$ 。^[6]^[7] 更一般地說，對任何簡併度為d和最大度為Δ的圖，圖平方的簡併度為O(dΔ)，因此許多不是平面圖的稀疏圖其平方的着色數與Δ成比例。

儘管最大度為Δ的非平面圖平方的着色數最壞情況是與Δ²成比例，對於高圍長的圖來說其往往更小，通常在這種情況下量級為O(Δ²/log Δ)。^[8]

確定為圖平方着色需要的顏色數是NP困難，即使在平面圖中也是如此。^[9]

哈密頓性

每個連通圖的立方必然包含一個哈密頓循環。^[10]一個連通圖的平方不一定滿足哈密頓性，它是否滿足哈密頓性是NP完備的。^[11]然而，根據弗萊施納定理，2-頂點連通圖的平方總是滿足哈密頓性的。^[12]

計算複雜度

一個有n 個頂點和m條邊的圖的k次冪可以通過從每個頂點開始執行廣度優先搜索來確定到所有其他頂點的距離，從而在時間O(mn)中計算出來。如果A是一個圖的鄰接矩陣，修改主對角線的非零元素，那麼A^k的非零項給出了圖的k次冪的鄰接矩陣，由此可以在矩陣乘法時間的對數因子內構造出第k次冪的時間量。^[13]

樹的k次冪可以在輸入圖的尺寸上用時間線性的方式識別。^[14]

給定一個圖，判斷它是否是另一個圖的平方是NP完全的。^[15]此外，對於給定的數字k≥2，確定一個圖是否是另一個圖的k次冪，或是二分圖的k次冪，是NP完全的。^[16]

導出子圖

二分圖G的半二分是 $G 2$ 的子圖，其為將 $G$ 平分為兩部分的一部分。平面圖的半二分是地圖圖，超立方圖的半二分是半立方圖。^[17]^[18]

葉冪是由樹的葉導出的樹的次冪子圖。 $k$ 葉冪是指數為 $k$ 的葉冪。^[19]

參考文獻

^ Bondy, Adrian; Murty, U. S. R., Graph Theory, Graduate Texts in Mathematics 244, Springer: 82, 2008, ISBN 9781846289699
^ Weisstein, Eric W. (編). Wolfram MathWorld (首頁). at MathWorld--A Wolfram Web Resource. Wolfram Research, Inc. （英語）.
^ Todinca, Ioan, Coloring powers of graphs of bounded clique-width, Graph-theoretic concepts in computer science, Lecture Notes in Comput. Sci. 2880, Springer, Berlin: 370–382, 2003, MR 2080095, doi:10.1007/978-3-540-39890-5_32 .
^ ^4.0 ^4.1 Agnarsson, Geir; Halldórsson, Magnús M., Coloring powers of planar graphs, Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '00), San Francisco, California, USA: 654–662, 2000 .
^ Formann, M.; Hagerup, T.; Haralambides, J.; Kaufmann, M.; Leighton, F. T.; Symvonis, A.; Welzl, E.; Woeginger, G., Drawing graphs in the plane with high resolution, SIAM Journal on Computing, 1993, 22 (5): 1035–1052, MR 1237161, doi:10.1137/0222063 .
^ Kramer, Florica; Kramer, Horst, A survey on the distance-colouring of graphs, Discrete Mathematics, 2008, 308 (2-3): 422–426, MR 2378044, doi:10.1016/j.disc.2006.11.059 .
^ Molloy, Michael; Salavatipour, Mohammad R., A bound on the chromatic number of the square of a planar graph, Journal of Combinatorial Theory, Series B, 2005, 94 (2): 189–213, MR 2145512, doi:10.1016/j.jctb.2004.12.005 .
^ Alon, Noga; Mohar, Bojan, The chromatic number of graph powers, Combinatorics, Probability and Computing, 2002, 11 (1): 1–10, MR 1888178, doi:10.1017/S0963548301004965 .
^ 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).
^ Bondy & Murty (2008), p. 105.
^ Underground, Polly, On graphs with Hamiltonian squares, Discrete Mathematics, 1978, 21 (3): 323, MR 0522906, doi:10.1016/0012-365X(78)90164-4 .
^ Diestel, Reinhard, 10. Hamiltonian cycles, Graph Theory (PDF) corrected 4th electronic, 2012 [2019-06-26], （原始內容 (PDF)存檔於2012-06-17） .
^ Hammack, Richard; Imrich, Wilfried; Klavžar, Sandi, Handbook of Product Graphs, Discrete Mathematics and Its Applications 2nd, CRC Press: 94, 2011, ISBN 9781439813058 .
^ Chang, Maw-Shang; Ko, Ming-Tat; Lu, Hsueh-I, Linear-Time Algorithms for Tree Root Problems, Algorithmica, 2015, 71 (2): 471–495, doi:10.1007/s00453-013-9815-y .
^ Motwani, R.; Sudan, M., Computing roots of graphs is hard, Discrete Applied Mathematics, 1994, 54: 81–88, doi:10.1016/0166-218x(94)00023-9 .
^ Le, Van Bang; Nguyen, Ngoc Tuy, Hardness results and efficient algorithms for graph powers, Graph-Theoretic Concepts in Computer Science: 35th International Workshop, WG 2009, Montpellier, France, June 24-26, 2009, Revised Papers, Lecture Notes in Computer Science 5911, Berlin: Springer: 238–249, 2010, ISBN 978-3-642-11408-3, MR 2587715, doi:10.1007/978-3-642-11409-0_21 .
^ Chen, Zhi-Zhong; Grigni, Michelangelo; Papadimitriou, Christos H., Map graphs, Journal of the ACM, 2002, 49 (2): 127–138, MR 2147819, arXiv:cs/9910013 , doi:10.1145/506147.506148 .
^ Shpectorov, S. V., On scale embeddings of graphs into hypercubes, European Journal of Combinatorics, 1993, 14 (2): 117–130, MR 1206617, doi:10.1006/eujc.1993.1016 .
^ Nishimura, N.; Ragde, P.; Thilikos, D.M., On graph powers for leaf-labeled trees, Journal of Algorithms, 2002, 42: 69–108, doi:10.1006/jagm.2001.1195 .

[1] Bondy, Adrian; Murty, U. S. R., Graph Theory, Graduate Texts in Mathematics 244, Springer: 82, 2008, ISBN 9781846289699

[2] Weisstein, Eric W. (編). Wolfram MathWorld (首頁). at MathWorld--A Wolfram Web Resource. Wolfram Research, Inc. （英語）.

[3] Todinca, Ioan, Coloring powers of graphs of bounded clique-width, Graph-theoretic concepts in computer science, Lecture Notes in Comput. Sci. 2880, Springer, Berlin: 370–382, 2003, MR 2080095, doi:10.1007/978-3-540-39890-5_32 .

[ah00-4] 4.0 ^4.1 Agnarsson, Geir; Halldórsson, Magnús M., Coloring powers of planar graphs, Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '00), San Francisco, California, USA: 654–662, 2000 .

[5] Formann, M.; Hagerup, T.; Haralambides, J.; Kaufmann, M.; Leighton, F. T.; Symvonis, A.; Welzl, E.; Woeginger, G., Drawing graphs in the plane with high resolution, SIAM Journal on Computing, 1993, 22 (5): 1035–1052, MR 1237161, doi:10.1137/0222063 .

[6] Kramer, Florica; Kramer, Horst, A survey on the distance-colouring of graphs, Discrete Mathematics, 2008, 308 (2-3): 422–426, MR 2378044, doi:10.1016/j.disc.2006.11.059 .

[7] Molloy, Michael; Salavatipour, Mohammad R., A bound on the chromatic number of the square of a planar graph, Journal of Combinatorial Theory, Series B, 2005, 94 (2): 189–213, MR 2145512, doi:10.1016/j.jctb.2004.12.005 .

[8] Alon, Noga; Mohar, Bojan, The chromatic number of graph powers, Combinatorics, Probability and Computing, 2002, 11 (1): 1–10, MR 1888178, doi:10.1017/S0963548301004965 .

[9] 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] Bondy & Murty (2008), p. 105.

[11] Underground, Polly, On graphs with Hamiltonian squares, Discrete Mathematics, 1978, 21 (3): 323, MR 0522906, doi:10.1016/0012-365X(78)90164-4 .

[12] Diestel, Reinhard, 10. Hamiltonian cycles, Graph Theory (PDF) corrected 4th electronic, 2012 [2019-06-26], （原始內容 (PDF)存檔於2012-06-17） .

[13] Hammack, Richard; Imrich, Wilfried; Klavžar, Sandi, Handbook of Product Graphs, Discrete Mathematics and Its Applications 2nd, CRC Press: 94, 2011, ISBN 9781439813058 .

[14] Chang, Maw-Shang; Ko, Ming-Tat; Lu, Hsueh-I, Linear-Time Algorithms for Tree Root Problems, Algorithmica, 2015, 71 (2): 471–495, doi:10.1007/s00453-013-9815-y .

[15] Motwani, R.; Sudan, M., Computing roots of graphs is hard, Discrete Applied Mathematics, 1994, 54: 81–88, doi:10.1016/0166-218x(94)00023-9 .

[16] Le, Van Bang; Nguyen, Ngoc Tuy, Hardness results and efficient algorithms for graph powers, Graph-Theoretic Concepts in Computer Science: 35th International Workshop, WG 2009, Montpellier, France, June 24-26, 2009, Revised Papers, Lecture Notes in Computer Science 5911, Berlin: Springer: 238–249, 2010, ISBN 978-3-642-11408-3, MR 2587715, doi:10.1007/978-3-642-11409-0_21 .

[17] Chen, Zhi-Zhong; Grigni, Michelangelo; Papadimitriou, Christos H., Map graphs, Journal of the ACM, 2002, 49 (2): 127–138, MR 2147819, arXiv:cs/9910013 , doi:10.1145/506147.506148 .

[18] Shpectorov, S. V., On scale embeddings of graphs into hypercubes, European Journal of Combinatorics, 1993, 14 (2): 117–130, MR 1206617, doi:10.1006/eujc.1993.1016 .

[19] Nishimura, N.; Ragde, P.; Thilikos, D.M., On graph powers for leaf-labeled trees, Journal of Algorithms, 2002, 42: 69–108, doi:10.1006/jagm.2001.1195 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]