一类图在小亏格曲面上的嵌入
2012-11-22黄元秋郑敦勇
魏 白，黄元秋，郭 婷，郑敦勇
(湖南师范大学数学与计算机科学学院，中国 长沙 410081)
研究图在不同亏格曲面上不等价的嵌入个数，可以归结为图的亏格分布和图的完全亏格分布.自从Gross和Furst[1]引入相关概念以来，相关学者得到了某些图类的亏格分布[2-13].由于图的亏格分布的研究是一个NP-难问题，因此目前有关亏格分布及完全亏格分布的结果较少.对于大部分图类，我们尚不能确定其亏格分布，尤其是完全亏格分布.然而图在不同亏格曲面上的嵌入通常是有相关关系的，所以研究图在球面，环面，射影平面，Klein瓶等小亏格曲面上的嵌入结构以及不等价的嵌入个数是一项有意义的工作.
以下3种运算不改变曲面的类型：运算1.Aaa-⟺A;运算2.AabBab⟺AcBc;运算3.AB⟺(Aa)(a-B).在这3种运算中，括号表示循环序，A，B均为字母的线性序.除运算2中的A和B允许为空集外，其余均为非空集合.事实上，以上运算确定了一类拓扑等价，记为“～”.由此可以导出下面3种拓扑等价关系：
关系1.AxByCx-Dy-E～ADCBExyx-y-;
关系2.AxBxC～AB-Cxx;
关系3.Axxyzy-z-～Axxyyzz.
1 引理和定义
引理1[10]设曲面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设S为不可定向曲面.若S=AxByCx-Dy-,则S的亏格至少是3.
证由关系1，S=AxByCx-Dy-～ADCBExyx-y-.不妨设S1=ADCBE,这里E是空集.则S～S1xyx-y-.由于S为不可定向曲面，则S1为不可定向曲面，且其亏格至少为1.由引理1知，S的亏格至少为3.
引理3设S为不可定向曲面，若S=AxByCyDx或S=AxByCxDy-,则S的亏格至少为2.
证若S=AxByCyDx，由关系2，S=AxByCyDx～AxBC-Dxyy～AD-CB-yyxx,由引理1知，S的亏格至少为2；若S=AxByCxDy-,由关系2，S=AxByCxDy-～AC-y-B-Dy-xx～AC-D-Bxxy-y-,由引理1知，S的亏格至少为2.
定义1若曲面S=AxByCxDy，则称边x和y在曲面S中交错；若曲面S=AxBxCyDy,则称x和y在曲面S中平行，其中(x)和(y)分别表示边x和边y的上标(即“+”或“-”).
引理4设S是射影平面，则其多边形表示中的任意2条边，若都是扭边，则必定交错，否则必定平行.
证由引理2和引理3易得.
定义2设A是一个字母循环序，则由A中的某些字母按原来的相对顺序组成的字母的循环序，称为A的子列.
引理5在曲面S的多边形表示中，若其子列也是某个曲面S1的多边形表示，则S1的亏格必定不大于S的亏格.
证由引理1易得.
2 主要结论
如果n个顶点的路的每条边都是双重边，并且两端点都各自有一个环，那么这样的图称之为鹅卵石路图(cobblestone path),长度为n,记为Jn。文献[6]已经得到了鹅卵石路图Jn的完全亏分布.分别用两顶点(不妨设为u,v),剖分Jn两端的环，并且用一条边a连接u和v,得到的图记为Gn+2(见图1).
2.1 Gn在球面S上的嵌入
首先在Gn中选定一棵生成树(如图1中粗边所示)，设其n个点分别为u1,u2,…,un,且ei=uiui+1(1≤i≤n-1),a=u1un.将每条余树边从中间切断，即可得到Gn的一棵联树(如图2).
图1 Gn
图2 Gn的一棵联树
由Gn是在球面S上的嵌入，可得到下列3个断言：
断言1所有的余树边均为非扭边.
证由引理6易得.
断言2余树边中，任意一条非扭边的2条半边必须在生成树的同侧.
断言3任意2条余树边，若均为非扭边，则必定平行.
证余树边中，若存在非扭边ei与ej交错，则由引理5知，Gn嵌入曲面S的亏格必定大于或等于1，这与S是球面矛盾.
定理1Gn在球面S上的嵌入个数为2n-1(n≥2).
2.2 Gn在射影平面S上的嵌入
Gn是在射影平面S上的嵌入.选定与图2所示的相同的生成树,下面就余树边a是否为扭边，分2种情形进行讨论:
嵌入情形1a为非扭边.
断言2余树边中，对于任意的扭边ei，它的2条半边ei,ei都必须在生成树的同侧.
证余树边中，若存在扭边ei，它的2条半边ei,ei在生成树的异侧，则扭边ei与非扭边a交错.由引理4，这与S是射影平面矛盾.
断言3余树边e1,e2,…,en-1中至少有一条扭边.
证由于Gn所嵌入的曲面S是不可定向的，则必定至少存在一条扭边，结论显然.
断言4若余树边ei(3≤i≤n-3)为扭边，则对于任意的j
证事实上，由断言3知，e1,e2,…,en-1中至少有一条扭边，不妨设这条扭边为ei(3≤i≤n-3),对于任意的j
断言5余树边ei(2≤i≤n-2)的2条邻边ei-1与ei+1不能同时为扭边.
证若ei-1与ei+1(2≤i≤n-2)同时为扭边，则ei-1与ei+1平行.由引理4知，这与S是射影平面矛盾.
由以上分析可知，余树边e1,e2,…,en-1中至少有一条扭边，不妨设为ei(3≤i≤n-3),对于任意的j
情形1.1余树边ei与它的一条邻边(不妨设为ei-1，2≤i≤n-1)为扭边，其余的余树边均为非扭边.
证由引理4知，扭边ei-1与ei(2≤i≤n-1)必定交错.由于ei-1与ei均为扭边，由断言2知，扭边ei-1与ei各自的2条半边均在生成树的同侧.因此由ei-1与ei所构成的Gn的子列只有图3～4所示2种情形.
图3 由ei-1与ei所构成的Gn的子列
图4 由ei-1与ei所构志的Gn的子列
情形1.2余树边中只有ei(1≤i≤n-1)为扭边，其余的均为非扭边.
综上，在嵌入情形1下，图Gn在射影平面上的嵌入个数为：(n-2)·2n-2+(n-1)·2n-1=(3n-4)·2n-2(n≥2).
嵌入情形2a为扭边.
断言2余树边中，对于任意的扭边ei，它的2条半边ei,ei必须在生成树的异侧.
证余树边中，若存在扭边ei,它的2条半边ei,ei在生成树的同侧，则扭边ei与a平行.由引理4知，这与S是射影平面矛盾.
断言3余树边中，若ei(3≤i≤n-3)为扭边，则对于任意的j
证余树边中，若ei为扭边，对于任意的j
断言4余树边ei的2条邻边ei-1与ei+1不能同时为扭边，2≤i≤n-2.
证若ei-1与ei+1同时为扭边，则ei-1与ei+1平行.由引理4，这与S是射影平面矛盾.
下面就余树边e1,e2,…,en-1中是否存在扭边分2种情况进行讨论.
情形2.1余树边e1,e2,…,en-1中不存在扭边.
由断言1和引理4知，余树边中，对于任意的非扭边ei,它的2条半边都必须在生成树的同侧，且必定平行.由组合计数原理知，在情形2.1下，图Gn在射影平面上的嵌入个数为2n-1.
情形2.2余树边e1,e2,…，en-1中存在扭边ei.
由断言3，余树边中，对于任意的j
情形2.2.1余树边a,ei与ei的一条邻边(不妨设为ei-1，2≤i≤n-1)为扭边，其余的n-3条余树边均为非扭边.
由断言2知，扭边ei-1与ei各自的2条半边均在生成树的异侧.由引理4知，ei-1与ei必须交错.则由ei-1与ei所构成的Gn的子列只有下图5～6所示2种情形:
图5 由ei-1与ei所构成的Gn的子列
图6 由ei-1与ei所构成的Gn的子列
子情形2.2.2余树边e1,e2,…,en-1中只有ei为扭边，即Gn中的非扭边为n-2条.
综上，在嵌入情形2下，图Gn在射影平面上的嵌入个数为：
2n-1+(n-2)·2n-2+(n-1)·2n-1=(3n-2)·2n-2(n≥2).
定理2Gn在射影平面S上的嵌入个数为(3n-3)·2n-1(n≥2).
证综合嵌入情形1及嵌入情形2，可得到图Gn在射影平面S上的嵌入个数为：
(3n-4)·2n-2+(3n-2)·2n-2=(3n-3)·2n-1(n≥2).
3 结束语
本文计算了一类图在球面以及射影平面上的嵌入个数.通过类似的方法，还可计算图Gn在环面，双环面及Klein瓶等小亏格曲面上的嵌入个数.这对于最终确定其亏格分布，尤其是完全亏格分布是非常有意义的，有助于深入分析图在不同曲面上的嵌入结构.本文作者已在这方面做了一些研究，但最终研究其亏格分布，尤其是完全亏格分布仍然是一项艰难的工作.
参考文献：
[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] 杨 艳，刘彦佩.两类四正则图的完全亏格分布[J].数学学报， 2007,50(5):1191-1200.
[9] 赵喜梅，刘彦佩.类圈图的亏格分布[J].数学物理学报, 2008,28(4):757-767.
[10] 刘彦佩.地图的代数原理[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] 刘新求，黄元秋，王 晶，等.两类项链图在射影平面上的嵌入[J].数学物理学报, 2011,31A(3):602-610.
[13] 刘新求，黄元秋，王 晶.多重圈梯图在射影平面上的嵌入个数[J].应用数学学报, 2010,33(2):317-327.
