頭條新聞

格雷圖是同類圖中最小的圖

作者：Eric W. Weisstein

2002年4月9日——在一篇提交給《離散數學》的論文中，一個數學家團隊解決了確定最小的三次圖的問題，該三次圖是半對稱的（即，邊傳遞但不是頂點傳遞的）。三次圖簡單來說是頂點和邊的集合（即，在圖論意義上的圖），其中每個頂點發出三條邊，不允許連線頂點到自身的環和兩個節點之間的多條邊（即，該圖是所謂的簡單圖）。邊傳遞圖是指在所謂的自同構群的某個元素下，任意兩條邊都是等價的圖，頂點傳遞圖的定義類似。圖的自同構群是從圖到自身並保留圖結構的函式的群（在群論意義上）。

Marion C. Gray 於 1932 年發現了一個具有 54 個頂點的半對稱三次圖，並由 Bouwer (1968) 首次發表。該圖（如上圖所示）被命名為 格雷圖，以紀念其最初的發現者。自發表以來，格雷圖一直是已知的最小的三次半對稱傳遞圖的例子。在即將發表的一篇論文中，Malnic 等人最終證明格雷圖實際上是最小的此類可能的圖。