主题
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.net.cn/CageGraph.html

主题分类