佩特森圖

维基百科,自由的百科全书
跳转至: 导航搜索
Petersen graph.svg


佩特森圖是一個特定的圖。朱利葉斯·佩特森在1898年構作它。雖然它以佩特森命名,但1886年已有人提及它了[1]

性質[编辑]

交叉數為2

最……[编辑]

  • 最小無橋而邊色數大於3的三次圖
  • 最小無橋而沒有哈密爾頓圈的三次圖
  • 最大半徑為2的三次圖
  • 最小的hypohamiltonian圖(原本無哈密爾頓圈,但除去任何一個頂點,便可有哈密爾頓圈)
  • 最小圍長為5的三次圖(唯一的(3,5)-cage graph和唯一的(3,5)-Moore graph。)

腳註[编辑]

  1. ^ 初見於A.B. Kempe的論文,參見英文版wiki(Petersen graph)