不可定向曲面上的最大亏格嵌入和最小亏格嵌入

李赵祥, 任韩

数学学报 ›› 2011, Vol. 54 ›› Issue (2) : 329-332.

PDF(364 KB)
PDF(364 KB)
数学学报 ›› 2011, Vol. 54 ›› Issue (2) : 329-332. DOI: 10.12386/A2011sxxb0034
论文

不可定向曲面上的最大亏格嵌入和最小亏格嵌入

    李赵祥1, 任韩2
作者信息 +

Maximum Genus Embeddings and Minimum Genus Embeddings in Non-orientable Surfaces

    Zhao Xiang LI1, Han REN2
Author information +
文章历史 +

摘要

研究了不可定向曲面上最大亏格嵌入的估计数, 得到了几类图的指数级 不可定向最大亏格嵌入的估计数的下界.利用电流图理论, 证明了完全图 K12s在不可定向曲面上至少有23s-2个最小亏格嵌入; 完全图 K12s+3在不可定向曲面上至少有22s个最小亏格嵌入; 完全图 K12s+7在不可定向曲面上至少有22s+1个最小亏格嵌入.

 

Abstract

In this paper, the estimation of the number of maximum genus nonorientable embeddings of graphs is studied, and an exponential lower bound for such number is found. Applying the theory of current graph, K12s has at least 23s-2 distinct minimum genus embedding in non-orientable surfaces; K12s+3 has at least 22s distinct minimum genus embedding in non-orientable surfaces; K12s+7 has at least 22s+1 distinct minimum genus embedding in non-orientable surfaces.

 

关键词

亏格嵌入 / 完全图 / 电流图

Key words

genus embedding / complete graph / current graph

引用本文

导出引用
李赵祥, 任韩. 不可定向曲面上的最大亏格嵌入和最小亏格嵌入. 数学学报, 2011, 54(2): 329-332 https://doi.org/10.12386/A2011sxxb0034
Zhao Xiang LI, Han REN. Maximum Genus Embeddings and Minimum Genus Embeddings in Non-orientable Surfaces. Acta Mathematica Sinica, Chinese Series, 2011, 54(2): 329-332 https://doi.org/10.12386/A2011sxxb0034

参考文献


[1] Bondy J. A., Murty U. S., Graph theory with applications, London: Macmillan, 1976.

[2] Huang Y. Q., On the Maximum Genus of Graphs, Ph.D.Dissertation, Beijing: Northern Jiaotong University, 1996 (in Chinese).

[3] Ren H., Bai Y., Exponentially many maximum genus embeddings and genus embedings for complete graphs, Science in Chinese, 2008, 38: 595-600.

[4] Lawrencenkno S., Negami S., White A. T., Three nonisomorphic triangulations of an orientable surface with the same complete graph, Discrete Mathmatics, 1994, 135: 367-369.

[5] Bonnington C. P., Grannell M. J., Griggs T. S., Siran J., Face 2-colourable triangular embeddings of complete graphs, J. Combin. Theory Ser. B, 1998, 74: 8-19.

[6] Liu Y. P., Embeddability in Graphs, London: Kluwer, 1995.

[7] Ringel G., Map Color Theorem, Berlin: Springer-Verlag, 1974.

[8] Liu Y. P., Map color theorem and surface embeddings of graphs, Math. Theory Prac., 1981, 1: 65-78.

[9] Ren H., Gao Y. B., Lower bound of the number of maximum genus embeddings and genus embeddings of K12s+7, Graphs and Comninatorics, Preprint.

基金

国家自然科学基金资助(10771225);中央民族大学自主科研项目资助

PDF(364 KB)

Accesses

Citation

Detail

段落导航
相关文章

/