佩特森圖

彼得森圖是一个由10个顶点和15条边构成的无向图。其最为人熟知的造型为一个五边形内包含一个五角星。彼得森圖由丹麦哥本哈根大学数学教授Julius Peter Christian Petersen于1898年提出。由于其有趣的性质，它常常用于证明中的例子或反例。

性質

交叉數為2

強正則圖。
半徑同直徑均為2。
点连通度和线连通度均为3。
最大独立集的大小为4。
點色數為3，邊色數為4。
非平面圖：子圖有完全圖 $K_{5}$ 和完全雙分圖 $K_{3,3}$ ，交叉數為2。
有哈密頓路徑而無哈密顿圈。
$K_{5}$ 的線圖的補圖。

最……

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

腳註

维基共享资源中相关的多媒体资源：佩特森圖

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.