佩特森图

Petersen graph.svg

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

性质

 
交叉数为2
  • 正则图
  • 半径同直径均为2。
  • 点连通度和线连通度均为3。
  • 最大独立集的大小为4。
  • 点色数为3,边色数为4。
  • 平面图:子图有完全图 完全双分图 ,交叉数为2。
  • 哈密顿路径而无哈密顿圈
  •  线图补图

最……

  • 最小无桥而边色数大于3的三次图(立方图)
  • 最小无桥而没有哈密尔顿圈的三次图
  • 最大半径为2的三次图
  • 最小的hypohamiltonian图(原本无哈密尔顿圈,但除去任何一个顶点,便可有哈密尔顿圈)
  • 最小围长为5的三次图(唯一的 -cage graph和唯一的 -Moore graph。)

脚注

  1. ^ Wikipedia Contributors. Julius Petersen. Wikipedia. [2020-12-25]. (原始内容存档于2021-02-11).