AAM  >> Vol. 2 No. 4 (November 2013)

    八个点的极小非环面图
    Minimal Nontoroidal Graphs on Eight Vertices

  • 全文下载: PDF(394KB) HTML    PP.186-190   DOI: 10.12677/AAM.2013.24025  
  • 下载量: 1,236  浏览量: 5,282   国家自然科学基金支持

作者:  

晁福刚,任 韩:华东师范大学数学系,上海

关键词:
嵌入亏格极小非环面图Embedding; Genus; Minimal Nontoroidal Graph

摘要:

借助于嵌入的技巧,证明了由K8,八个点的完全图,去掉K3,三角形,或K2,3,部集的点数为23的完全二部图,或K2∪K2∪P3,长度为1的两条路和长度为2的一条路的不交并,中的边得到的图是极小的非环面图。

Using the technique of embedding, we prove that the graphs obtained fromK8 , the complete graph on eight vertices, by deleting the edges ofK3 , a triangle, orK2,3 , the complete bipartite graph with 2 vertices and 3 vertices, orK2∪K2∪P3 , the disjoint union of two paths of length one and one path of length two, are minimal nontoroidal graphs.

文章引用:
晁福刚, 任韩. 八个点的极小非环面图[J]. 应用数学进展, 2013, 2(4): 186-190. http://dx.doi.org/10.12677/AAM.2013.24025

参考文献

[1] Thomassen, C. (1992) The Jordan-Schönflies theorem and the classification of surfaces. American Mathematical Monthly, 99, 116-130.
[2] Mohar, B. and Thomassen, C. (2001) Graphs on surfaces. Johns Hopkins University Press, London.
[3] Kuratowski, C. (1930) Sur le probléme des courbes gauches en topologie. Fundamenta Mathematicae, 15, 271-283.
[4] Heawood, P.J. (1890) Map colour theorem. The Quarterly Journal of Pure and Applied Mathematics, 24, 332-338.
[5] Ringel, G. and Youngs, J.W.T. (1968) Solution of the Heawood map-coloring problem. Proceedings of the National Academy of Sciences of the United States of America, 60, 438-455.
[6] Franklin, P. (1934) A six color problem. Journal of Mathematical Physics, 13, 363-369.
[7] Rringel, G. (1974) Map color theorem. Springer, Berlin.
[8] Thomassen, C. (1989) The graph genus problem is NP-complete. Journal of Algorithms, 10, 568-576.
[9] Thomassen, C. (1993) Five-coloring maps on surfaces. Journal of Combinatorial Theory, Series B, 59, 89-105.
[10] Thomassen, C. (1997) Color-critical graphs on a fixed surface. Journal of Combinatorial Theory, Series B, 70, 67-100.
[11] Thomassen, C. (2003) The chromatic number of a graph of girth 5 on a fixed surface. Journal of Combinatorial Theory, Series B, 87, 38-71.
[12] Chenette, N., Postle, L., Streib, N. and Thomas, R. (2012) Five-colorings graphs on the Klein bottle. Journal of Combinatorial Theory, Series B, 102, 1067-1098.
[13] Kawarayabashi, K.I., Král, D., Kynčl, J. and Lidický, B. (2009) 6-critical graphs on the Klein bottle. SIAM Journal on Discrete Mathematics, 23, 372-383.