圓梯中梯圖的虧格分布

曾建初

(昆明理工大學 學報編輯部,云南 昆明　650500)

?

圓梯中梯圖的虧格分布

曾建初

(昆明理工大學 學報編輯部,云南 昆明650500)

摘要：近幾十年來，拓撲圖論都是數學研究的一個重要領域,計算圖的虧格分布是拓撲圖論中的一個熱點內容.該文對圖的可定向虧格分布問題進行了研究，應用聯樹模型的方法,計算了一類新的3-正則圖——圓梯中梯圖的虧格分布.

關鍵詞：聯樹模型;虧格分布;圓梯中梯圖

0引言

近幾十年來，拓撲圖論都是數學研究的一個重要領域,計算圖的虧格分布是拓撲圖論中的一個熱點內容.人們研究圖的虧格分布,發現了很的數學方法.如劉彥佩教授聯樹模型[1-2].Mohar教授的矩陣模型[3].張湘林等[4]用迭代粘合法計算了一類5-正則圖的虧格分布..本文以聯樹模[1-2]為工具,受文獻[1-13]思想的啟發,計算了圓梯中梯圖——一類新的3-正則圖的虧格分布.如無特別說明,本文所說的虧格分布都是可定向的虧格分布.

1預備知識

引理1[1]設B,C,D,E,F是多邊形P的邊對應的帶符號的字母的線性排列,則

任何一個曲面,其多邊形表示都有唯一的一個標準形式:

引理3[1]任何圖G總能被嵌入可定向曲面.設n(G)為圖G在可定向曲面上不同嵌入的數目,則

這里:ni是度數為i的頂點的個數.

引理4[1]圖G在虧格為p的曲面上嵌入的數目,與樹T的選取無關.

gi(G)表示圖G在虧格為i(i≥0)可定向曲面上的不同嵌入的數目,圖G的可定向虧格分布多項式是:

這里n是圖G的參數.需要進一步了解的概念參見文獻[1].

2主要結果

把一個圓梯的每一條梯邊從中剖開,嵌入1個梯,這樣所形成的圖形叫做圓梯中梯圖,圖1是n+1條梯邊的圓梯中梯圖,記為Gn+1.圖2表示圖Gn+1的一個聯樹Jn.

圖1　圓梯圖Gn+1

圖2　圖Gn+1的一個聯樹Jn

根據聯樹(joint tree)Jn,有

表與之間關系表

引入如下3個映射ψi(i=1,2,3)[2]:

我們能夠把圓梯中梯圖的關聯曲面化簡為下面11類(a,b,c是不同的符號)：

經過計算,獲得

表1

定理2圓梯中梯圖Gn+1的聯樹對應的關聯曲面是下面的28=256類:

圓梯中梯圖Gn+1的虧格多項式是:

其中:C0=4g09(n)+4g010(n)+56g011(n),C1=4g19(n)+4g110(n)+56g111(n)+48g09(n)+48g010(n)+96g011(n),…,C2n=4g(2n)9(n)+4g(2n)10(n)+56g(2n)11(n)+48g(2n-1)9(n)+48g(2n-1)10(n)+96g(2n-1)11(n),C2n+1=48g(2n)9(n)+48g(2n)10(n)+96g(2n)11(n)

當n=1時,

C0=4×2+4×2+56×0=16

C1=4×86+4×86+56×64+48×2+48×2+96×0=4464

C2=4×168+4×168+56×192+48×(86+86)+96×64=26496

C3=48×(168+168)+96×192=34560

fG2(x)=16+4464x+26496x2+34560x3

當n=2時,

C0=16,C1=3568,C2=346112,C3=2935296

C4=7630848,C5=5861376

fG3(x)=16+3568x+346112x2+2935296x3+7630848x4+5861376x5

參考文獻：

[1]Yanpei Liu.Theory of Polyhedra[M].Beijing:Science press,2007.

[2]Wan L X,Liu Y P.On the embedding genus distribution of ladders and crosses[J].Applied mathematics letters,2009(22):738-742.

[3]Mohar B.An obstruction to embedding graphs in surfaces[J].Discrete math,1989(78):135-142.

[4]張湘林,黃元秋,郭婷.一類5-正則外平面圖的虧格分布[J].應用數學學報,2015(5):133-144.

[5]Zeng J,Liu Y,Hao R.Counting Orientable Embeddings by Genus for a Type of 3-Regular Graph[J].Graphs & Combinatorics,2012(1):133-142.

[6]任韓.曲面上圖染色綜述(上)[J].昆明理工大學學報:自然科學版,2016(1):130-148.

[7]劉彥佩.我所認識的拓撲圖論(Ⅰ):球面上十部曲[J].2013(1):105-108.

[8]譚秋月.若干圖類的平衡指標集[J].昆明理工大學學報:自然科學版,2014(6):136-140.

[9]吳躍生.非連通并圖I(K_(m,n))∪G的優美標號[J].昆明理工大學學報:自然科學版,2015(2):142-146.

[10]馬京成，馬登舉，朱王君.3-正則Halin圖的完美匹配數[J].昆明理工大學學報:自然科學版,2015(5):132-136.

[11]任韓.曲面上圖染色綜述(下)[J].昆明理工大學學報:自然科學版,2016(2):134-148.

[12]郝榮霞，李文俏，劉峰.梯圖的線圖的Tutte唯一性[J].昆明理工大學學報：自然科學版,2012(4):98-102.

[13]任韓，鐔松齡，馬登舉.稠密圖的三角剖分嵌入[J].昆明理工大學學報：自然科學版,2012(2):89-93.

Genus Distribution of Ladder of Circular Ladder Graphs

ZENG Jian-chu

(EditorialDepartmentofJournalofKunmingUniversityofScienceandTechnology,Kunming,Yunnan650500)

Abstract：In recent decades,topological graph theory has been an important field of mathematical research.Calculating the orientable genus distribution of graphs is a hot issue.In this paper,the orientable genus distribution of a class of graphs was studied by applying the method of the joint tree model,calculating the genus distribution of a new class of 3-regular graphs,ladder of circular ladder graphs.

Key words：joint tree model；orientable genus distribution；ladder of circular ladder graphs

收稿日期：2016-01-01

基金項目:云南省人才培養項目(KKSY201213063).

作者簡介：曾建初，1964年生,男,湖南漣源人,副教授，博士,研究方向:拓撲圖論.

中圖分類號：O157.5

文獻標識碼：A

文章編號：1671-9743(2016)05-0015-05