佩特森圖
此條目沒有列出任何參考或來源。 (2010年8月16日) |
彼得森圖是一個由10個頂點和15條邊構成的無向圖。其最為人熟知的造型為一個五邊形內包含一個五角星。彼得森圖由丹麥哥本哈根大學數學教授Julius Peter Christian Petersen於1898年提出。由於其有趣的性質,它常常用於證明中的例子或反例。
性質
- 強正則圖。
- 半徑同直徑均為2。
- 點連通度和線連通度均為3。
- 最大獨立集的大小為4。
- 點色數為3,邊色數為4。
- 非平面圖:子圖有完全圖和完全雙分圖,交叉數為2。
- 有哈密頓路徑而無哈密頓圈。
- 的線圖的補圖。
最……
- 最小無橋而邊色數大於3的三次圖(立方圖)
- 最小無橋而沒有哈密爾頓圈的三次圖
- 最大半徑為2的三次圖
- 最小的hypohamiltonian圖(原本無哈密爾頓圈,但除去任何一個頂點,便可有哈密爾頓圈)
- 最小圍長為5的三次圖(唯一的-cage graph和唯一的-Moore graph。)
腳註