主題
Search

籠圖

下載 Mathematica Notebook下載 Wolfram Notebook

一個 (v,g)-籠圖是一個 v-正則圖，其圍長為 g，並且具有最少可能的節點數。當 v 未明確指出時，術語 “g-籠” 通常指 (3,g)-籠。

籠圖列表可以在 Wolfram Language 中使用以下程式碼獲得GraphData["Cage"].

存在許多特殊情況 (Wong 1982)。(2,g)-籠是圈圖 C_g，(v,2)-籠是在兩個頂點上具有 v 條邊的多重圖，(v,3)-籠是完全圖 K_(v+1)，並且 (v,4)-籠是二部圖 K_(v,v)。

設 n(v,g) 為 (v,g)-籠圖中的頂點數。然後，下表總結了 n(v,g) 對於 g 和 v 從 3 到 7 的小值的精確已知值。值 n(3,11)=112 由 McKay等人 (1998) 發現。

gn(3,g)n(4,g)n(5,g)n(6,g)n(7,g)
SloaneA000066
345678
468101214
51019304050
61426426290
72467152294
83080170312
958275
1070384
11112
1212672827307812

對於 g>=5 和 v>=3 (Wong 1982)，計算 n(v,g) 在 (v,g)-籠中的頂點數非常困難。下界 n_l(v,g)>=n(v,g) 由下式給出

n_l(v,g)={(v(v-1)^((g-1)/2)-2)/(v-2) for g odd; (2(v-1)^(g/2)-2)/(v-2) for g even
(1)

(Tutte 1967, p. 70; Bollobás 1978, p. 105; Wong 1982)。對於 v=3，這給出了 n_l(3,g) 對於 g=1, 2, ... 的下限序列 4, 6, 10, 14, 22, 30, 46, 62, 94, 126, 190, 254, ... (OEIS A027383)，這與已知的實際值一致。

Sauer (1967ab) 獲得了已知的最佳上界

n_u(3,g)={4/3+(29)/(12)2^(g-2) for g odd; 2/3+(29)/(12)2^(g-2) for g even
(2)
n_u(v,g)={2(v-1)^(g-2) for g odd; 4(v-1)^(g-3) for g even,
(3)

對於 v>=4 (Wong 1982)。

下表總結了已知的籠圖。

(v,g)計數命名的籠子（或參考文獻）
(3,3)1完全圖 K_4
(3,4)1完全二部圖 K_(3,3)
(3,5)1Petersen 圖
(3,6)1Heawood 圖
(3,7)1McGee 圖
(3,8)1Tutte 8-籠
(3,9)18Biggs 和 Hoare (1980), Brinkmann et al. (1995)
(3,10)3Balaban 10-籠, Harries 圖, Harries-Wong 圖
(3,11)1Balaban 11-籠; Balaban (1973), Myrvold 和 McKay
(3,12)1Tutte 12-籠; Polster et al. (1998, p. 179)
(4,3)1完全圖 K_5
(4,4)1完全二部圖 K_(4,4)
(4,5)1Robertson 圖
(4,6)1Wong (1982)
(4,7)>=1Exoo (2007)
(4,8)>=1Royle
(4,12)>=1廣義十二邊形 GD(1,3)
(5,3)1完全圖 K_6
(5,4)1完全二部圖 K_(5,5)
(5,5)4Wong 圖, Foster 籠, Meringer 圖, Robertson-Wegner 圖
(5,6)>=1Royle
(5,7)>=1Royle
(5,8)>=1Royle
(5,12)>=1Royle
(6,3)1完全圖 K_7
(6,4)1完全二部圖 K_(6,6)
(6,7)>=1Royle
(6,8)>=1Royle
(6,12)>=1Royle
(7,3)1完全圖 K_8
(7,4)1完全二部圖 K_(7,7)
(7,5)1Hoffman-Singleton 圖
(8,8)>=1Royle
(9,8)>=1Royle
(10,8)>=1Royle
(12,8)>=1Royle
(14,6)>=1Royle
(14,8)>=1Royle
CageGraphs3

立方 (v=3) 籠最初由 Tutte (1947) 討論，但籠圖的深入研究直到 Erdős 和 Sachs (1963) 發表文章後才開始。對於所有 g>=3，都存在一個 (3,g)-籠，並且 (3,g)-籠對於 g=3 到 8 是唯一的。上面說明了已知 (3,g)-籠的選擇 (Read 和 Wilson 1998, pp. 271-272)。唯一的 (3,8)-籠是Tutte 8-籠 (Read 和 Wilson 1998, p. 271)。第一個 (3,9)-籠由 Biggs 和 Hoare (1980) 發現，Brinkmann et al. (1995) 完成了一項詳盡的搜尋，產生了所有 18 個 (3,9)-籠 (Royle)。Holton 和 Sheehan (1993, p. 197) 說明了其中一個。O'Keefe 和 Wong (1980; Read 和 Wilson 1998, p. 272) 發現了三個 (3,10)-籠。McKay 和 W. Myrvold 的計算表明，(3,11)-籠必須有 112 個頂點 (McKay et al. 1998, Royle)，並且 Balaban (1973) 發現了單個已知示例，有時被稱為Balaban 10-籠。Myrvold 和 McKay 隨後證明了 112 個頂點上的最小圖是唯一的 (B. D. McKay, 私人通訊, 2003 年 5 月 20 日)。對於 g=3, 4, ...，非同構 (3,g) 籠的數量由 1, 1, 1, 1, 1, 1, 18, 3, 1, 1, ... 給出 (OEIS A052453; Gould 1988, Royle)。

CageGraphs4

上面說明了已知的 (4,g)-籠 (Wong 1982)。2007 年 3 月，Exoo et al. 最終確定了一個 (4,7)-籠。

CageGraphs5

上面顯示了一些 (5,g)-籠 (Wong 1982)。Meringer (1999) 表明存在四個 (5,5)-籠，儘管 Wong (1982) 指出只存在三個這樣的籠。

Hoffman-Singleton 圖是一個 (7,5)-籠。

對於公式 (1) 的下界給出實際頂點數的籠圖，被稱為 Moore 圖。

另請參閱

Balaban 10-籠, Cayley 圖, 立方圖, 超額, Foster 籠, Harries 圖, Harries-Wong 圖, Heawood 圖, Hoffman-Singleton 圖, McGee 圖, Meringer 圖, Moore 圖, Petersen 圖, 正則圖, Robertson 圖, Robertson-Wegner 圖, Tutte 8-籠, Wong 圖

使用 探索

參考文獻

Balaban, A. T. "Trivalent Graphs of Girth Nine and Eleven and Relationships among the Cages." Rev. Roumaine Math. Pures Appl. 18, 1033-1043, 1973.Biggs, N. L. Ch. 23 in Algebraic Graph Theory, 2nd ed. Cambridge, England: Cambridge University Press, 1993.Biggs, N. L. "Constructions for Cubic Graphs of Large Girth." LSE Tech Report 97-11.Biggs, N. L. and Hoare, M. J. "A Trivalent Graph with 58 Vertices and Girth 9." Disc. Math. 30, 299-301, 1980.Bollobás, B. Extremal Graph Theory. New York: Academic Press, 1978.Bondy, J. A. and Murty, U. S. R. Graph Theory with Applications. New York: North Holland, pp. 236-239, 1976.Brinkmann, G.; McKay, B. D.; and Saager, C. "The Smallest Cubic Graphs of Girth Nine." Combin., Probability, and Computing 5, 1-13, 1995.Brouwer, A. E. "Cages." http://www.win.tue.nl/~aeb/graphs/cages/cages.html.Brouwer, A. E.; Cohen, A. M.; and Neumaier, A. "Cages." §6.9 in Distance Regular Graphs. New York: Springer-Verlag, 1989.Erdős, P. and Sachs, H. "Reguläre graphen gegebener Taillenweite mit minimaler Knotenzahl." Wiss. Z. Uni. Halle (Math. Nat.) 12, 251-257, 1963.Exoo, G.; McKay, B.; and Myrvold, W. "A (4,7)-Cage." Preprint. March 2007. http://isu.indstate.edu/ge/CAGES/g4.7.67.Exoo, G. and Jajcay, R. "Dynamic Cage Survey." Electr. J. Combin. 15, 2008.Gould, R. (Ed.). Graph Theory. Menlo Park, CA: Benjamin-Cummings, 1988.Harary, F. Graph Theory. Reading, MA: Addison-Wesley, pp. 174-175, 1994.Holton, D. A. and Sheehan, J. Ch. 6 in The Petersen Graph. Cambridge, England: Cambridge University Press, 1993.McKay, B. D.; Myrvold, W.; and Nadon, J. "Fast Backtracking Principles Applied to Find New Cages." 9th Annual ACM-SIAM Symposium on Discrete Algorithms, January 1998. pp. 188-191.Meringer, M. "Fast Generation of Regular Graphs and Construction of Cages." J. Graph Th. 30, 137-146, 1999.O'Keefe, M. and Wong, P. K. "A Smallest Graph of Girth 10 and Valency 3." J. Combin. Th. B 29, 91-105, 1980.Pisanski, T. and Randić, M. "Bridges between Geometry and Graph Theory." In Geometry at Work: Papers in Applied Geometry (Ed. C. A. Gorini). Washington, DC: Math. Assoc. Amer., pp. 174-194, 2000.Polster, B. A Geometrical Picture Book. New York: Springer-Verlag, p. 179, 1998.Read, R. C. and Wilson, R. J. An Atlas of Graphs. Oxford, England: Oxford University Press, pp. 263 and 271-274, 1998.Royle, G. "Cubic Cages." http://school.maths.uwa.edu.au/~gordon/remote/cages/.Royle, G. "Cages of Higher Valency." http://school.maths.uwa.edu.au/~gordon/remote/cages/allcages.html.Sauer, N. "Extremaleigneschaften regulärer Graphen gegebener Taillenweite, I." Österreich. Akad. Wiss. Math. Natur. Kl. S.-B. II 176, 9-25, 1967a.Sauer, N. "Extremaleigneschaften regulärer Graphen gegebener Taillenweite, II." Österreich. Akad. Wiss. Math. Natur. Kl. S.-B. II 176, 27-43, 1967b.Skiena, S. Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, pp. 191 and 221, 1990.Sloane, N. J. A. Sequences A000066/M1013, A027383, A037233, and A052453 in "The On-Line Encyclopedia of Integer Sequences."Tutte, W. T. "A Family of Cubical Graphs." Proc. Cambridge Philos. Soc. 43, 459-474, 1947.Tutte, W. T. Connectivity in Graphs. Toronto, Canada: Toronto University Press, pp. 70-83, 1967.Wong, P. K. "Cages--A Survey." J. Graph Th. 6, 1-22, 1982.

在 中被引用

籠圖

請這樣引用

Weisstein, Eric W. “籠圖。” 來自 —— 資源。 https://mathworld.tw/CageGraph.html

主題分類