兩類圖在球面和環面上的嵌入

摘 要 圖在不同虧格曲面上的嵌入往往有相關關系， 因此， 分析一些圖類在小虧格曲面上的嵌入是一項有意義的工作. 本文利用劉彥佩教授提出的嵌入的聯樹模型研究了兩類圖在球面和環面上的嵌入特征，分別得到了它們的嵌入個數.

關鍵詞 曲面； 虧格； 嵌入； 聯樹

中圖分類號 O157.5 文獻標識碼 A 文章編號 1000-2537（2016）03-0075-05

Abstract Embedding numbers of graphs on distinct genus surfaces are always related. Therefore， analyzing embedding numbers of graphs on lower genus surfaces is important to determine their genus distributions and total genus distributions. Based on the model of joint tree introduced by Liu， this paper calculates the embedding number of two type graphs on sphere and torus.

Key words surface； genus； embedding； joint tree

本文中關于曲面、嵌入和虧格等概念均與文獻[1]一致. 圖的曲面嵌入是拓撲圖論的一個重要分支， 特別地， 研究圖在不同虧格曲面上的嵌入個數即圖的虧格分布和完全虧格分布問題是其中重要研究方向之一. 上世紀九十年代起， 國內外很多學者做出了一些有價值的研究[2-7]， 但是還遠遠未解決這個問題， 對于大部分圖類， 還不能得出其虧格分布和完全虧格分布， 此問題被證明為NP難問題. 于是， 有學者轉而研究一些圖在特定曲面上的嵌入， 譬如研究圖在球面、射影平面、環面及Klein平面等小虧格曲面上的嵌入. 近年來， 利用劉彥佩教授提出的聯樹模型和曲面運算理論[8]， 國內一些學者在這方面做出了一些有意義的結論[9-11].本文作者亦在聯樹模型的基礎上， 研究了兩類項鏈圖在射影平面上的嵌入[12]， 本文擬在此基礎上， 進一步研究兩類圖在球面和環面上的嵌入.

1 曲面運算理論和聯樹模型

為了表述方便， 本文對曲面運算理論和聯樹模型進行簡要介紹[8].

曲面運算理論：任何一個曲面都可以看作是由一個正多邊形“粘合”而成， 所以曲面可以用多邊形來表示， 具體的表示理論參考文獻[8]. 下面僅列出本文敘述中要用到的三種運算和三種關系.

參考文獻：

[1] GROSS J L， TUCKER T W. Topological graph theory[M]. New York： Dover Publicaions， Inc， 1987.

[2] GROSS J L， FURST M L. Hierarchy of imbedding distribution invariants of graph[J]. J Graph Theory， 1987，11：205-220.

[3] GURST M L， GROSS J L， STATEMAN R. Genus distributions for two classes of graphs[J]. J Combin Theory Ser B， 1989，46：22-36.

[4] GROSS J L， ROBBINS D P， TUCKER T W. Genus distributions for bouquets of circles[J]. J Combin Theory Ser B， 1989，47：292-306.

[5] KWAK J H， LEE J. Genus polynomials of dippoles of circles[J]. Discrete Math， 1993，33：115-125.

[6] CHEN J， GROSS J L， RIEPER R G. Overlap matrics and total imbedding distrbution[J]. Discrete Math， 1994，128：73-94.

[7] CHEN Y C， LIU Y P. The total embedding distributions of cacti and necklaces[J]. Acta Math Sinica （Eng Ser）， 2006，22（5）：1583-1590.

[8] 劉彥佩. 地圖的代數原理[M]. 北京：高等教育出版社， 2006.

[9] 楊 艷， 劉彥佩. 兩類四正則圖的完全虧格分布[J]. 數學學報， 2007，50（5）：1190-1200.

[10] 趙喜梅， 劉彥佩. 類圈圖的虧格分布[J]. 數學物理學報， 2008，28（4）：757-767.

[11] 魏 白， 黃元秋， 郭 婷， 等. 一類圖在小虧格曲面上的嵌入[J]. 湖南師范大學自然科學學報， 2012，35（5）：24-29.

[12] 劉新求， 黃元秋. 兩類項鏈圖在射影平面上的嵌入[J]. 數學物理學報， 2011，31（3）：601-610.

（編輯 HWJ）