主題
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. (作者連結) 貢獻

使用 探索

參考文獻

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." 來自 Web 資源。 https://mathworld.tw/Snark.html

主題分類