一類(lèi)圖在小虧格曲面上的嵌入

魏 白，黃元秋，郭 婷，鄭敦勇

(湖南師范大學(xué)數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院，中國(guó) 長(zhǎng)沙 410081)

研究圖在不同虧格曲面上不等價(jià)的嵌入個(gè)數(shù)，可以歸結(jié)為圖的虧格分布和圖的完全虧格分布.自從Gross和Furst[1]引入相關(guān)概念以來(lái)，相關(guān)學(xué)者得到了某些圖類(lèi)的虧格分布[2-13].由于圖的虧格分布的研究是一個(gè)NP-難問(wèn)題，因此目前有關(guān)虧格分布及完全虧格分布的結(jié)果較少.對(duì)于大部分圖類(lèi)，我們尚不能確定其虧格分布，尤其是完全虧格分布.然而圖在不同虧格曲面上的嵌入通常是有相關(guān)關(guān)系的，所以研究圖在球面，環(huán)面，射影平面，Klein瓶等小虧格曲面上的嵌入結(jié)構(gòu)以及不等價(jià)的嵌入個(gè)數(shù)是一項(xiàng)有意義的工作.

以下3種運(yùn)算不改變曲面的類(lèi)型：運(yùn)算1.Aaa-?A;運(yùn)算2.AabBab?AcBc;運(yùn)算3.AB?(Aa)(a-B).在這3種運(yùn)算中，括號(hào)表示循環(huán)序，A，B均為字母的線性序.除運(yùn)算2中的A和B允許為空集外，其余均為非空集合.事實(shí)上，以上運(yùn)算確定了一類(lèi)拓?fù)涞葍r(jià)，記為“～”.由此可以導(dǎo)出下面3種拓?fù)涞葍r(jià)關(guān)系：

關(guān)系1.AxByCx-Dy-E～ADCBExyx-y-;

關(guān)系2.AxBxC～AB-Cxx;

關(guān)系3.Axxyzy-z-～Axxyyzz.

1 引理和定義

引理1[10]設(shè)曲面S1是可定向曲面且虧格為p，曲面S2是不可定向曲面且虧格為q.

(1) 若曲面S～S1xyx-y-,則曲面S是可定向的，且虧格為p+1;

(2) 若曲面S～S2xyx-y-,則曲面S是不可定向的，且虧格為q+2;

(3) 若曲面S～S1xx,則曲面S是不可定向的，且虧格為2p+1;

(4) 若曲面S～S2xx,則曲面S是不可定向的，且虧格為q+1.

引理2設(shè)S為不可定向曲面.若S=AxByCx-Dy-,則S的虧格至少是3.

證由關(guān)系1，S=AxByCx-Dy-～ADCBExyx-y-.不妨設(shè)S1=ADCBE,這里E是空集.則S～S1xyx-y-.由于S為不可定向曲面，則S1為不可定向曲面，且其虧格至少為1.由引理1知，S的虧格至少為3.

引理3設(shè)S為不可定向曲面，若S=AxByCyDx或S=AxByCxDy-,則S的虧格至少為2.

證若S=AxByCyDx，由關(guān)系2，S=AxByCyDx～AxBC-Dxyy～AD-CB-yyxx,由引理1知，S的虧格至少為2；若S=AxByCxDy-,由關(guān)系2，S=AxByCxDy-～AC-y-B-Dy-xx～AC-D-Bxxy-y-,由引理1知，S的虧格至少為2.

定義1若曲面S=AxByCxDy，則稱(chēng)邊x和y在曲面S中交錯(cuò)；若曲面S=AxBxCyDy,則稱(chēng)x和y在曲面S中平行，其中(x)和(y)分別表示邊x和邊y的上標(biāo)(即“+”或“-”).

引理4設(shè)S是射影平面，則其多邊形表示中的任意2條邊，若都是扭邊，則必定交錯(cuò)，否則必定平行.

證由引理2和引理3易得.

定義2設(shè)A是一個(gè)字母循環(huán)序，則由A中的某些字母按原來(lái)的相對(duì)順序組成的字母的循環(huán)序，稱(chēng)為A的子列.

引理5在曲面S的多邊形表示中，若其子列也是某個(gè)曲面S1的多邊形表示，則S1的虧格必定不大于S的虧格.

證由引理1易得.

2 主要結(jié)論

如果n個(gè)頂點(diǎn)的路的每條邊都是雙重邊，并且兩端點(diǎn)都各自有一個(gè)環(huán)，那么這樣的圖稱(chēng)之為鵝卵石路圖(cobblestone path),長(zhǎng)度為n,記為Jn。文獻(xiàn)[6]已經(jīng)得到了鵝卵石路圖Jn的完全虧分布.分別用兩頂點(diǎn)(不妨設(shè)為u,v),剖分Jn兩端的環(huán)，并且用一條邊a連接u和v,得到的圖記為Gn+2(見(jiàn)圖1).

2.1 Gn在球面S上的嵌入

首先在Gn中選定一棵生成樹(shù)(如圖1中粗邊所示)，設(shè)其n個(gè)點(diǎn)分別為u1,u2,…,un,且ei=uiui+1(1≤i≤n-1),a=u1un.將每條余樹(shù)邊從中間切斷，即可得到Gn的一棵聯(lián)樹(shù)(如圖2).

圖1 Gn

圖2 Gn的一棵聯(lián)樹(shù)

由Gn是在球面S上的嵌入，可得到下列3個(gè)斷言：

斷言1所有的余樹(shù)邊均為非扭邊.

證由引理6易得.

斷言2余樹(shù)邊中，任意一條非扭邊的2條半邊必須在生成樹(shù)的同側(cè).

斷言3任意2條余樹(shù)邊，若均為非扭邊，則必定平行.

證余樹(shù)邊中，若存在非扭邊ei與ej交錯(cuò)，則由引理5知，Gn嵌入曲面S的虧格必定大于或等于1，這與S是球面矛盾.

定理1Gn在球面S上的嵌入個(gè)數(shù)為2n-1(n≥2).

2.2 Gn在射影平面S上的嵌入

Gn是在射影平面S上的嵌入.選定與圖2所示的相同的生成樹(shù),下面就余樹(shù)邊a是否為扭邊，分2種情形進(jìn)行討論:

嵌入情形1a為非扭邊.

斷言2余樹(shù)邊中，對(duì)于任意的扭邊ei，它的2條半邊ei,ei都必須在生成樹(shù)的同側(cè).

證余樹(shù)邊中，若存在扭邊ei，它的2條半邊ei,ei在生成樹(shù)的異側(cè)，則扭邊ei與非扭邊a交錯(cuò).由引理4，這與S是射影平面矛盾.

斷言3余樹(shù)邊e1,e2,…,en-1中至少有一條扭邊.

證由于Gn所嵌入的曲面S是不可定向的，則必定至少存在一條扭邊，結(jié)論顯然.

斷言4若余樹(shù)邊ei(3≤i≤n-3)為扭邊，則對(duì)于任意的ji+1，余樹(shù)邊ej均為非扭邊.

證事實(shí)上，由斷言3知，e1,e2,…,en-1中至少有一條扭邊，不妨設(shè)這條扭邊為ei(3≤i≤n-3),對(duì)于任意的ji+1，若存在ej為扭邊，則扭邊ei與ej必定平行.由引理4知，這與S是射影平面矛盾.

斷言5余樹(shù)邊ei(2≤i≤n-2)的2條鄰邊ei-1與ei+1不能同時(shí)為扭邊.

證若ei-1與ei+1(2≤i≤n-2)同時(shí)為扭邊，則ei-1與ei+1平行.由引理4知，這與S是射影平面矛盾.

由以上分析可知，余樹(shù)邊e1,e2,…,en-1中至少有一條扭邊，不妨設(shè)為ei(3≤i≤n-3),對(duì)于任意的ji+1,ej均為非扭邊，且ei-1,ei+1不能同時(shí)為扭邊.因此下面對(duì)余樹(shù)邊ei(2≤i≤n-2)的2條鄰邊ei-1與ei+1是否為扭邊分2種子情形討論：

情形1.1余樹(shù)邊ei與它的一條鄰邊(不妨設(shè)為ei-1，2≤i≤n-1)為扭邊，其余的余樹(shù)邊均為非扭邊.

證由引理4知，扭邊ei-1與ei(2≤i≤n-1)必定交錯(cuò).由于ei-1與ei均為扭邊，由斷言2知，扭邊ei-1與ei各自的2條半邊均在生成樹(shù)的同側(cè).因此由ei-1與ei所構(gòu)成的Gn的子列只有圖3～4所示2種情形.

圖3 由ei-1與ei所構(gòu)成的Gn的子列

圖4 由ei-1與ei所構(gòu)志的Gn的子列

情形1.2余樹(shù)邊中只有ei(1≤i≤n-1)為扭邊，其余的均為非扭邊.

綜上，在嵌入情形1下，圖Gn在射影平面上的嵌入個(gè)數(shù)為：(n-2)·2n-2+(n-1)·2n-1=(3n-4)·2n-2(n≥2).

嵌入情形2a為扭邊.

斷言2余樹(shù)邊中，對(duì)于任意的扭邊ei，它的2條半邊ei,ei必須在生成樹(shù)的異側(cè).

證余樹(shù)邊中，若存在扭邊ei,它的2條半邊ei,ei在生成樹(shù)的同側(cè)，則扭邊ei與a平行.由引理4知，這與S是射影平面矛盾.

斷言3余樹(shù)邊中，若ei(3≤i≤n-3)為扭邊，則對(duì)于任意的ji+1,余樹(shù)邊ej均為非扭邊.

證余樹(shù)邊中，若ei為扭邊，對(duì)于任意的ji+1，若存在ej也為扭邊，顯然，扭邊ei與ej平行.由引理4知，這與S是射影平面矛盾.

斷言4余樹(shù)邊ei的2條鄰邊ei-1與ei+1不能同時(shí)為扭邊，2≤i≤n-2.

證若ei-1與ei+1同時(shí)為扭邊，則ei-1與ei+1平行.由引理4，這與S是射影平面矛盾.

下面就余樹(shù)邊e1,e2,…,en-1中是否存在扭邊分2種情況進(jìn)行討論.

情形2.1余樹(shù)邊e1,e2,…,en-1中不存在扭邊.

由斷言1和引理4知，余樹(shù)邊中，對(duì)于任意的非扭邊ei,它的2條半邊都必須在生成樹(shù)的同側(cè)，且必定平行.由組合計(jì)數(shù)原理知，在情形2.1下，圖Gn在射影平面上的嵌入個(gè)數(shù)為2n-1.

情形2.2余樹(shù)邊e1,e2,…，en-1中存在扭邊ei.

由斷言3，余樹(shù)邊中，對(duì)于任意的ji+1，所有的ej均為非扭邊，且由斷言4知，ei-1與ei+1不能同時(shí)為扭邊.因此下面就余樹(shù)邊ei(2≤i≤n-2)的2條鄰邊ei-1與ei+1是否為扭邊分2種子情形討論：

情形2.2.1余樹(shù)邊a,ei與ei的一條鄰邊(不妨設(shè)為ei-1，2≤i≤n-1)為扭邊，其余的n-3條余樹(shù)邊均為非扭邊.

由斷言2知，扭邊ei-1與ei各自的2條半邊均在生成樹(shù)的異側(cè).由引理4知，ei-1與ei必須交錯(cuò).則由ei-1與ei所構(gòu)成的Gn的子列只有下圖5～6所示2種情形:

圖5 由ei-1與ei所構(gòu)成的Gn的子列

圖6 由ei-1與ei所構(gòu)成的Gn的子列

子情形2.2.2余樹(shù)邊e1,e2,…,en-1中只有ei為扭邊，即Gn中的非扭邊為n-2條.

綜上，在嵌入情形2下，圖Gn在射影平面上的嵌入個(gè)數(shù)為：

2n-1+(n-2)·2n-2+(n-1)·2n-1=(3n-2)·2n-2(n≥2).

定理2Gn在射影平面S上的嵌入個(gè)數(shù)為(3n-3)·2n-1(n≥2).

證綜合嵌入情形1及嵌入情形2，可得到圖Gn在射影平面S上的嵌入個(gè)數(shù)為：

(3n-4)·2n-2+(3n-2)·2n-2=(3n-3)·2n-1(n≥2).

3 結(jié)束語(yǔ)

本文計(jì)算了一類(lèi)圖在球面以及射影平面上的嵌入個(gè)數(shù).通過(guò)類(lèi)似的方法，還可計(jì)算圖Gn在環(huán)面，雙環(huán)面及Klein瓶等小虧格曲面上的嵌入個(gè)數(shù).這對(duì)于最終確定其虧格分布，尤其是完全虧格分布是非常有意義的，有助于深入分析圖在不同曲面上的嵌入結(jié)構(gòu).本文作者已在這方面做了一些研究，但最終研究其虧格分布，尤其是完全虧格分布仍然是一項(xiàng)艱難的工作.

參考文獻(xiàn)：

[1] GROSS J L, FURST M L. Hierarchy for imbedding-distribution invariants of graph[J]. J Graph Theory, 1987,11(2):205-220.

[2] CHEN Y C, LIU Y P, WANG T. The total embedding distributions of cacti and necklaces[J]. Acta Math Sinica, 2006,22(5):1583-1590.

[3] TESAR E H. Genus distribution of ringel ladders[J]. Discrete Math, 2000,216(1-3):235-252.

[4] WAN L X, LIU Y P. Orientable embedding distribution by genus for certain type of non-planar graphs(I)[J].Ars Combin, 2006,79:97-105.

[5] WAN L X, LIU Y P. Orientable embedding distribution for certain types of graphs[J]. J Combin Theory,Ser B, 2008,98(1):19-32.

[6] CHEN J, GROSS J L, RIEPER R G. Overlap matrices and total imbedding distributions[J]. Discrete Math, 1994,128(1-3):73-94.

[7] GROSS J L, ROBBINS D P, TUCKER T W. Genus distributions for bouquets of circles[J]. J Combin Theory, Ser B, 1989,47(3):292-306.

[8] 楊 艷，劉彥佩.兩類(lèi)四正則圖的完全虧格分布[J].數(shù)學(xué)學(xué)報(bào)， 2007,50(5):1191-1200.

[9] 趙喜梅，劉彥佩.類(lèi)圈圖的虧格分布[J].數(shù)學(xué)物理學(xué)報(bào), 2008,28(4):757-767.

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

[11] YANG Y, LIU Y P. Flexibility of embeddings of bouquets of circles on the projective plane and Klein bottle[J]. Electron J Combin, 2007,14:#R80.

[12] 劉新求，黃元秋，王 晶，等.兩類(lèi)項(xiàng)鏈圖在射影平面上的嵌入[J].數(shù)學(xué)物理學(xué)報(bào), 2011,31A(3):602-610.

[13] 劉新求，黃元秋，王 晶.多重圈梯圖在射影平面上的嵌入個(gè)數(shù)[J].應(yīng)用數(shù)學(xué)學(xué)報(bào), 2010,33(2):317-327.