圍長 (圖論)

圖論中,一個圖的圍長定義為這個圖所包含的最短長。[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