主题
Search

Snark


术语“snark”最早由 Gardner (1976) 推广,作为一类最小的立方图,其边色数 为 4,并具有一定的连通性要求。(根据 Vizing 定理,每个立方图边色数要么是三,要么是四,因此 snark 对应于四的特殊情况。)因此,Snarks 是 2 类图。Snarks 有几种定义。按照 Brinkmann 等人 (2013) 的说法,弱 snark 被称为循环 4 边连通的立方图,其边色数 为 4,围长至少为 4;而(通用、无限定或强)snark 是循环 4 边连通的立方图,其边色数 为 4,围长至少为 5(Holton 和 Sheehan 1993,第 87 页,Brinkmann 等人 2013)。

彼得森图是最小的 snark,Tutte 推测所有 snarks 都具有彼得森图 图次要项。Robertson、Sanders、Seymour 和 Thomas 在 2001 年证明了这一猜想,他们使用了扩展的方法来重新证明四色定理。所有 snarks 必然是非平面非哈密顿的。

在 1946 年 Blanuša snarks 发表之前(Blanuša 1946),彼得森图一直是唯一已知的 snark。Tutte 发现了下一个 snark,Blanche Descartes 重新发现了它,并发现了一些相关的 snarks。Szekeres (1973) 发现了第五个 snark,Isaacs (1975) 证明存在无限个 snarks 族,Martin Gardner (1976) 提议将这些图命名为“snarks”。在较小的 snarks 中,有一个具有 10 个顶点(彼得森图),两个具有 18 个顶点(Blanuša snarks),六个具有 20 个顶点(其中一个是花 snark J_5),以及 20 个具有 22 个顶点的。

n=10、12、14、... 个节点的 snarks 数量为 1、0、0、0、2、6、20、38、280、2900、28399、293059、3833587、60167732、... (OEIS A130315; Brinkmann 和 Steffen 1998)。

双星 snark 有 30 个顶点,而 Szekeres snark 有 50 个顶点。Goldberg 发现了另一类 snarks(Goldberg snarks)。其他的 snarks 包括在 26 个顶点上的两个 Celmins-Swart snarks (Read and Wilson 1998, p. 281),在 22 个顶点上的第一个和第二个 Loupekine snarks (Read and Wilson 1998, p. 279) 以及在 50 个顶点上的 Watkins snark (Read and Wilson 1998, p. 281)。请注意,Read 和 Wilson (1998, pp. 276 和 281-282) 对花 snarks J_5J_7J_9J_(11) 的图示不正确。

Snarks

下表总结了一些已命名的 snarks,如上所示。


另请参阅

几乎哈密顿图, 几乎次哈密顿图, Blanuša Snarks, Celmins-Swart Snarks, 2 类图, 立方图, 循环边连通度, Descartes Snarks, 双星 Snark, 边色数, 花 Snark, Goldberg Snark, 非哈密顿图, 彼得森图, Szekeres Snark, Vizing 定理, Watkins Snark, 弱 Snark

此条目的部分内容由 Ed Pegg, Jr. (作者链接) 贡献

使用 Wolfram|Alpha 探索

参考文献

Blanusa, D. "Problem cetiriju boja." Glasnik Mat. Fiz. Astr. Ser. II. 1, 31-42, 1946.Brinkmann, G. and Steffen, F. "Snarks and Reducibility." Ars Combin. 50, 292-296, 1998.Brinkmann, G.; Goedgebeur, J.; Hägglund, J.; and Markström, K. "Generation and Properties of Snarks." J. Comb. Th. 103, 468-488, 2013.Cameron, P. J.; Chetwynd, A. G.; and Watkins, J. J. "Decomposition of Snarks." J. Graph Th. 11, 13-19, 1987.Chetwynd, A. G. and Wilson, R. J. "Snarks and Supersnarks." In The Theory and Applications of Graphs (Ed. Y. Alavi et al. ). New York: Wiley, pp. 215-241, 1981.Descartes, B. "Network-Colourings." Math. Gaz. 32, 67-69, 1948.Fiorini, S. "Hypohamiltonian Snarks." In Graphs and Other Combinatorial Topics (Ed. M. Fiedler). Leipzig, Germany: Teubner, 1983.Gardner, M. "Mathematical Games: Snarks, Boojums, and Other Conjectures Related to the Four-Color-Map Theorem." Sci. Amer. 234, No. 4, 126-130, 1976.Goldberg, M. K. "Construction of Class 2 Graphs with Maximum Vertex Degree 3." J. Combin. Th. Ser. B 31, 282-291, 1981.Hägglund, J. and Markström, K. "On Stable Cycles and Cycle Double Covers of Graphs with Large Circumference." Disc. Math. 312, 2540-2544, 2012.Holton, D. A. and Sheehan, J. "Snarks." Ch. 3 in The Petersen Graph. Cambridge, England: Cambridge University Press, pp. 79-111, 1993.House of Graphs. "Snarks." https://hog.grinvin.org/Snarks#snarks.Isaacs, R. "Infinite Families of Nontrivial Trivalent Graphs Which Are Not Tait Colorable." Amer. Math. Monthly 82, 221-239, 1975.Nedela, R. and Skoviera, M. "Decompositions and Reductions of Snarks." J. Graph Th. 22, 253-279, 1983.Read, R. C. and Wilson, R. J. An Atlas of Graphs. Oxford, England: Oxford University Press, pp. 263 and 276-281, 1998.Royle, G. "Snarks." http://people.csse.uwa.edu.au/gordon/remote/cubics/#snarks.Sloane, N. J. A. Sequence A130315 in "The On-Line Encyclopedia of Integer Sequences."Steffen, E. "Classification and Characterisations of Snarks." SFB-Preprint 94-056. Bielefeld, Germany: Universität Bielefeld, 1994.Szekeres, G. "Polyhedral Decompositions of Cubic Graphs." Bull. Austral. Math. Soc. 8, 367-387, 1973.Watkins, J. J. "Snarks." Ann. New York Acad. Sci. 576, 606-622, 1989.West, D. B. Introduction to Graph Theory, 2nd ed. Englewood Cliffs, NJ: Prentice-Hall, pp. 304-306, 2000.

请这样引用

Pegg, Ed Jr.Weisstein, Eric W. "Snark." 来自 MathWorld--Wolfram Web 资源。 https://mathworld.net.cn/Snark.html

主题分类