主題
Search

奇圖

下載 Mathematica 筆記本下載 Wolfram Notebook

階為 n 的奇圖 O_n 是一個圖，其頂點由 {1,...,2n-1} 的 (n-1)-子集給出，使得當且僅當相關的子集是不相交的時，兩個頂點透過邊連線（Biggs 1993，Ex. 8f，p. 58）。需要注意的是，基於 {1,...,2n+1} 的 n-子集定義奇圖的約定有時也被使用，導致索引移動一位（例如，West 2000，Ex. 1.1.28，p. 17）。

根據使用普遍約定的奇圖定義，O_n 中的節點數為 (2n-1; n-1)，其中 (n; k) 是一個二項式係數。對於 n=1、2、...，前幾個值是 1、3、10、35、126、... (OEIS A001700)。

OddGraphs

O_1 同構於 單例圖，O_2 同構於 三角形圖 C_3，O(3) 同構於 彼得森圖 (Skiena 1990, p. 162)。克內澤圖 K(n,k) 是奇圖的推廣，其中 O_n 對應於 K(2n-1,n-1)。二部克內澤圖 是奇圖的 二部雙圖 的推廣，其中 O_n 對應於 H(2n-1,n-1) (像 O_n 一樣，它是 距離傳遞圖；Brouwer et al. 1989, p. 222)。

O_n 是 正則 的，頂點度 為 n，圖直徑 為 n-1 (Biggs 1976)。O_n 的 周長 對於 n>=4 為 6 (West 2000, p. 17; 將索引約定調整為更常見的基於 n-1 子集的定義)。

奇圖是 距離傳遞 的，因此也是 距離正則 的。它們也是 自同構圖 (Biggs 1976)。據推測，O_n 是 1 類圖，除了 n=3 和 n 為 2 的冪的情況 (Fiorini and Wilson 1977)。

Balaban (1972) 展示了 n=4 和 5 的 哈密頓環，Meredith 和 Lloyd (1972, 1973) 找到了 n=6 和 7 的環，Mather (1976) 展示了 n=8 的 哈密頓環 (Shields and Savage)。

由於奇圖是 克內澤圖 的一個特例，它的 獨立數 從 alpha(K(n,k)) 的值得出，如

alpha(O_n)=(2n-2; n-2).

奇圖在 Wolfram 語言 中實現為FromEntity[Entity["Graph", {"Odd", n]]，並且小奇圖的預計算屬性實現為GraphData[{"Odd", n}].

另請參閱

完全圖, 距離正則圖, 距離傳遞圖, 克內澤圖, 奇頂點, 彼得森圖

使用 探索

參考文獻

Balaban, A. T. "Chemical Graphs, Part XIII; Combinatorial Patterns." Rev. Roumaine Math. Pures Appl. 17, 3-16, 1972.Biggs, N. L. "Automorphic Graphs and the Krein Condition." Geom. Dedicata 5, 117-127, 1976.Biggs, N. L. Algebraic Graph Theory, 2nd ed. Cambridge, England: Cambridge University Press, p. 161, 1993.Brouwer, A. E. "Odd Graphs." http://www.win.tue.nl/~aeb/drg/graphs/Odd.html.Brouwer, A. E.; Cohen, A. M.; and Neumaier, A. Distance-Regular Graphs. New York: Springer-Verlag, 1989.DistanceRegular.org. "Odd Graphs." http://www.distanceregular.org/indexes/oddgraphs.html.Fiorini, S. and Wilson, R. Edge-Colourings of Graphs. Pittman, 1977.Mather, M. "The Rugby Footballers of Croam." J. Combin. Theory Ser. B 20, 62-63, 1976.Meredith, G. H. J. and Lloyd, E. K. "The Hamiltonian graphs O_4 to O_7." In Combinatorics (Proc. Conf. Combinatorial Math., Math. Inst., Oxford, 1972). Southend: Inst. Math. Appl., pp. 229-236, 1972.Meredith, G. H. J. and Lloyd, E. K. "The Footballers of Croam." J. Combin. Theory Ser. B 15, 161-166, 1973.Mütze, T. "On Hamilton Cycles in Graphs Defined by Intersecting Set Systems." Not. Amer. Soc. 74, 583-592, 2024.Shields, I. and Savage, C. D. "A Note on Hamilton Cycles in Kneser Graphs." http://www.cybershields.com/publications/kneser3.pdf.Skiena, S. Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, 1990.Sloane, N. J. A. Sequence A001700/M2848 in "The On-Line Encyclopedia of Integer Sequences."West, D. B. "The Odd graph O_k." Exercise 1.1.28 in Introduction to Graph Theory, 2nd ed. Englewood Cliffs, NJ: Prentice-Hall, p. 17, 2000.

在 上被引用

奇圖

請按如下方式引用

Weisstein, Eric W. "Odd Graph." 來自 Web 資源。 https://mathworld.tw/OddGraph.html

主題分類