围长 (图论)

图论中,一个图的围长定义为这个图所包含的最短长。[1] 若这个图是无环图,它的围长则定义做无穷大[2] 举例来说,4-环(正方形)的围长是 4。

笼 (Cage)

最小的围长为 g 的三次图(3-正则图)称做 g-笼(或是 (3,g)-笼)。佩特森图是唯一的 5-笼,Heawood graph 则是唯一的 6-笼,McGee graph 是唯一的 7-笼,Tutte eight cage 是唯一的 8-笼。[3] 对特定的围长来说,可能会存在不只一个笼。比如,存在三个不同构的 10-笼,分别都有 70 条边:Balaban 10-cage、Harries graph、Harries–Wong graph。

围长与图染色

给定任意正整数  ,存在一幅图,其围长不小于 ,同时色数不小于 。例如,格勒奇图英语Grötzsch graph无三角形,且色数为 ,然后重复采用梅切尔斯基英语Mycielskian构造法(格勒奇图亦是以此法可得),即得任意大色数而无三角形的图。埃尔德什·帕尔最先用概率方法英语probabilistic method证明一般的结论:[4]

 个顶点的随机图,每两点之间各自独立地以 概率连边,则当 趋向无穷时,大概率(趋向于 )该图中 长度不逾 的环总数不超过 ,同时没有 大小的独立集。所以,在每个短环中移除一点,馀下的子图至少有 点,围长大于 ,但染色时,每种颜色的点数不能超过 ,即需要至少 种色。

若不用概率论证,亦可明确构造围长和色数皆大的图,例如有限域上某些线性群凯莱图[5]此类例子同时属拉马努金图英语Ramanujan graphs扩展系数大。

参考文献

  1. ^ R. Diestel, Graph Theory, p.8. 3rd Edition, Springer-Verlag, 2005
  2. ^ Weisstein, Eric W. (编). Girth. at MathWorld--A Wolfram Web Resource. Wolfram Research, Inc. [2017-06-16]. (原始内容存档于2020-08-04) (英语). 
  3. ^ Brouwer, Andries E., Cages, [2017-06-16], (原始内容存档于2020-08-04) .
  4. ^ Erdős, Paul. Graph theory and probability [图论与概率]. Canadian Journal of Mathematics. 1959, 11: 34–38. doi:10.4153/CJM-1959-003-9 (英语). 
  5. ^ Davidoff, Giuliana; Sarnak, Peter; Valette, Alain, Elementary number theory, group theory, and Ramanujan graphs, London Mathematical Society Student Texts 55, Cambridge University Press, Cambridge, 2003, ISBN 0-521-82426-5, MR 1989434, doi:10.1017/CBO9780511615825