主題
Search

廣義 Moore 圖


廣義 Moore 圖是一個度為 r正則圖,其中從任意頂點出發,距離為 d=0, 1, ... 的頂點計數分別為 1, r, r(r-1), r(r-1)^2, r(r-1)^3, ..., 最後一個距離計數不一定填滿。也就是說,除了最後一個級別可能需要補齊剩餘部分外,所有級別都是滿的。或者,圍長與樸素界限允許的最大值一樣大,直徑與樸素界限允許的最小值一樣小。換句話說,廣義 Moore 圖是一個正則圖,使得頂點對之間的平均距離達到樸素下界。

GeneralizedMooreGraphs

具有 n=1, 2, ... 個節點的廣義 Moore 圖的數量分別為 0, 0, 0, 1, 1, 4, 3, 13, 21, ... (OEIS A088933)。

GeneralizedMooreGraphsCubic

具有 n=2, 4, 6, ... 個節點的三次廣義 Moore 圖的數量分別為 0, 1, 2, 2, 1, 2, 7, 6, 1, 1, ... (OEIS A005007)。

對於每個度數,是否存在無限多個廣義 Moore 圖是一個未解決的問題。


參見

Moore 圖, 正則圖

使用 探索

參考文獻

McKay, B. D. 和 Stanton, R. G. "廣義 Moore 圖問題的現狀。" 收錄於 組合數學 VI:1978 年 8 月在澳大利亞阿米代爾舉行的第六屆澳大利亞組合數學會議論文集。 紐約:施普林格出版社,第 21-31 頁,1979 年。Sloane, N. J. A. 序列 A005007/M0199 和 A088933,來自“整數序列線上百科全書”。

在 中被引用

廣義 Moore 圖

以此引用

Weisstein, Eric W. "廣義 Moore 圖。" 來自 Web 資源。 https://mathworld.tw/GeneralizedMooreGraph.html

主題分類