图的次幂

在数学的一个分支图论中，一个无向图的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]