主题
Search

图的周长

图的周长是图中任何最长圈的长度。哈密顿图在 n>1 个顶点上的周长为 n。

对于循环图，所有相邻顶点 (i,j) 上绕道矩阵的最大元素 a_(ij) 比周长小 1。

自补图的图周长为 n（即，该图是哈密顿图）、n-1 或 n-2 (Furrigia 1999, p. 51)。

下表总结了各种非哈密顿图的图周长。

类别周长
哑铃图n
(n,n)-主教图{n^2/2 for n even; (n^2+1)/2 for n odd
书图 S_(n+1) square P_26
完全二分图 K_(m,n)，对于 min(m,n)>12min(m,n)
(m,n)-锥图{2m for m<=n; m+n otherwise
齿轮图2n
网格图 P_m square P_n{mn-1 for m,n odd; mn otherwise
网格图 P_l square P_m square P_n{lmn-1 for l,m,n odd; lmn otherwise
舵图n+1
(n,n)-骑士图{14 for n=4; n^2 for even n>4; n^2-1 for odd n>2
平底锅图n
日晒图 C_n circledot K_1n
网状图2n
轮图 W_nn
(m,n)-风车图n

另请参阅

近哈密顿图, 绕道矩阵, 围长, 图的圈, 图的直径, 图的离心率, 图的半径, 哈密顿数, 最长路径

使用 探索

参考文献

Dirac, G. "Some Theorems on Abstract Graphs." Proc. London Math. Soc. 2, 69-81, 1952.Farrugia, A. "Self-Complementary Graphs and Generalisations: a Comprehensive Reference Manual." Aug. 1999. http://www.alastairfarrugia.net/sc-graph/sc-graph-survey.pdf.Harary, F. Graph Theory. Reading, MA: Addison-Wesley, p. 13, 1994.Li, H. "Generalizations of Dirac's Theorem in Hamiltonian Graph Theory--A Survey." Disc. Math. 313, 2034-2053, 2013.Skiena, S. Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, p. 192, 1990.Yuan, L-.T. "Circumference, Minimum Degree and Clique Number." Elec. J. Combin. 31, No. 4, Article P4.64, 2024.Zamfirescu, T. "On Longest Paths and Circuits in Graphs." Math. Scand. 38, 211-239, 1976.

在 中引用

图的周长

请这样引用

韦斯坦因，埃里克·W. "图的周长。" 来自 网络资源。 https://mathworld.net.cn/GraphCircumference.html

主题分类