兩類圖在球面和環(huán)面上的嵌入

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

關(guān)鍵詞 曲面； 虧格； 嵌入； 聯(lián)樹

中圖分類號 O157.5 文獻(xiàn)標(biāo)識碼 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

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

1 曲面運算理論和聯(lián)樹模型

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

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

參考文獻(xiàn)：

[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] 劉彥佩. 地圖的代數(shù)原理[M]. 北京：高等教育出版社， 2006.

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

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

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

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

（編輯 HWJ）