两类项链图在射影平面上的嵌入

两类项链图在射影平面上的嵌入 毪 物理 两类项链图在射影平面上的嵌入 刘新求黄元秋王晶欧阳章东 (湖南师范大学数学与计算机科学学院长沙410081) 摘要:图在不同亏格曲面上的嵌入往往有相关关系,因此,分析一些图类在低亏格曲面上的嵌 入是一项有意义的工作,有助于最终确定图的亏格分布和完全亏格分布.该文利用刘彦佩教授 提出的嵌入的联树模型得出了两类项链图在射影平面上的嵌入特征和嵌入个数. 关键词:曲面;亏格;嵌入;联树. MR(2000)主分类:05C10中图分类号:O157.5文献标识码:A 文章编号:1003—3998(2011)03—602—09 1引言 本文中的曲面指的是无边缘的紧闭二维流形,分为可定向曲面和不可定向曲面.在球面 上增加P个"手柄"得到亏格为P的可定向曲面Op;在球面上增加q个"交叉帽"得到亏 格为q的不可定向曲面?a.图G在曲面S上的一个嵌入是指一个1-1连续映射h:G—S, 使得S—h(C)的每个连通分支均与开圆盘同胚.图G在曲面上的两个嵌入h:G—s和 g:G—称为等价的是指,存在一个可定向保持同胚映射f:S—S,使得fOh:g. 曲面也可以用平面上一个偶数条边的正多边形来示:边两两成对,成对的边用同 一个 字母表示,每边分配一个方向,用上标"+"(通常省略)和"一"区分,按某一方向依次记录 正多边形的边,得到带上标字母的循环序,这叫做曲面的多边形表示.平面,环面,射影平 面,Klein平面可分别表示为Oo:ao,一,01=aba—b一,?】=00,?2=aabb.一般地,分别用 P = ?.ibin6i=1 表示亏格为P和q的可定向和不可定向曲面,其中P0,q1,并称之为曲面的标准型代数 表示.如果用字母a表示的一组对边的方向相反,则称a为非扭边,如果用字母a表示的 一 组对边的方向相同,则称.为扭边. 以下三种运算不改变曲面的类型. 运算1Aaa甘A. 收稿日期:2009—06—23;修订日期:2010—04—30 E—mail:liuxinqiuxie~sina.com;hyqq@hunnu.edu.cn 基金项目:国家自然科学基金(10771062,10901048)教育部新世纪优秀人才支持(07—0276)和湖南省研究 生科研创新项目(CX2009B098)资助. 通讯作者 n 0n = No.3刘新求等:两类项链图在射影平面上的嵌入603 运算2AabBab兮AcBc. 运算3AB?(Aa)(a—B). 在以上三种运算中,括号表示循环序,和B均为字母的线性序,除运算2中和B 允许为空外,其余均为非空.事实上以上运算确定一类拓扑等价,记作",",由此可以导出 下面三种拓扑等价关系. 关系1AxByCx—Dy—EADCBExyx,Y一. 关系2AxBxCAB—Cxx. 关系3Axxyzy—,Axxyyzz. 一 般地,若A=ala2a3…a.n,则0…a3一a2一a一1叫做的逆,记作,一0o.运 用以上三种关系,任何一个曲面都可以化为标准型代数表示. 研究图在不同亏格曲面上的不等价的嵌入个数可以归结为图的亏格分布和完全亏格分 布这类问题,自从Gross和Furst[]引入相关概念以来,一些学者已经得出了一些图类的亏 格分布或完全亏格分布【-7】.对于大部分图类,我们尚不能确定其亏格分布尤其是完全亏格 分布,然而图在不同亏格曲面上的嵌入往往有相关关系,所以研究图在球面,环面,射影平 面,Klein瓶上的嵌入结构及其个数是一项有意义的工作. 刘彦佩教授创建的嵌入的联树模型【8J对研究图的亏格分布和完全亏格分布有着上 的突破和改进:给定图G=(E)的一棵生成树,然后将每条余树边赋予一个字母,并将 每条余树边从中间切断,得到两条用同一字母表示的边,此时所得的图形为树,叫做G的 联树.设余树边的数目为,从一个节点出发沿和旋走遍联树的所有边,依次记录余树边 的字母(生成树的边则不用记录),得到一个2边形,赋予每条边一个方向,同样用上标 区分方向,这样就得到了图G的关联曲面.图的关联曲面和图的嵌入之间存在一一对应, 关联曲面的亏格为,既表明在此旋系下,图G嵌入在亏格为k的可定向或不可定向曲面 上,且不同的关联曲面对应不同的嵌入.因此我们用图的关联曲面的结构来分析图在曲面上 的嵌入.近期有学者作出了一些结论[9--11].本文亦在联树模型的基础上得出了两类项链图 在射影平面上嵌入的个数及结构特征. 2引理和定义 引理2.1[8_设曲面1是可定向曲面且亏格为P,曲面s2是不可定向曲面且亏格为q. (1)若曲面S=,.~lxyx,Y一,则曲面s是可定向的且亏格为P+l; (2)若曲面S=xyx,Y一,则曲面S是不可定向的且亏格为q+2; (3)若曲面S—S1XX,则曲面s是不可定向的且亏格为2p+1; (4)若曲面S=$2xx,则曲面是不可定向的且亏格为q十1. 引理2.2设S为不可定向曲面,若S=AxByCx—Dy一,则的亏格至少为3. 证根据关系1,S=AxByCx—Dy一一ADCBxyx—Y一,令=ADCB,则S2必定为不 可定向曲面,亏格至少为1,又根据引理2.1,曲面s的亏格至少为3.1 引理2.3设为不可定向曲面,若S-二AxByCyDx或S—AxByCxDy一,则S的亏 格至少为2. 证若S=AxByCyDx,根据关系2,有 S=AxByCyDx,AxBC—Dxyy—AD—B—yyxx 又根据引理2.1,曲面S的亏格至少为2 数学物理V_01.31A 若S=AxByCxDy,根据关系2,有 S=AxByCxDy一,AC—y—B—Dy—XXAC—D—Bxxy—Y一 又根据引理2.1,曲面s的亏格也至少为2. 引理2.4[.]环束B在球面上的嵌入个数为 9.(Bmm 引理2.5【12]对于nk0有 一 )(n一)!(n+k) 定义2.1若曲面S=AxByCx.()Dy(圳,则称边X和Y在曲面中交错,若曲面 S—AxBx()CyDy(,则称边和Y在曲面s中平行,其中E()和E()分别表示边X和 Y的上标(+或一). 引理2.6设是射影平面,则其多边形表示中的任意两条边,若都是扭边,则必定交 错,否则必定平行. 证根据引理2.2和引理2.3易得.1 引理2.7设S是射影平面,则其曲面多边形表示必定为如下形式 S=alAla2A2…r上k.1A+102A+2???akA2k 其中a1,a2,…,a为全体扭边,且00或为空,i=1,2,…,2k,七1. 证首先根据引理2.6,射影平面多边形表示中任意两条扭边必定交错.设al,a2,…,n 为所有扭边,则 S=alAla2A2???n01+1n2+2…akA2k. 另一方面,因为中的边均为非扭边,如果存在某个不为空且AiOo,1i2k, 则必为以下两种情形之一. (1)AOp且P之1,则根据关系2和引理2.1,其亏格必至少为3,与'5|是射影平面矛 盾; (2)某条边在A中只出现一次,设为X.则必定存在某个J:1Jk,使得和X一之 间恰出现一次(否则和X一只能都在A中),从而 S=aj…x…??? 由引理2.3,S的亏格至少为2,与是射影平面矛盾.定理得证.1 引理2.8曲面S—ala2…aA,Oo当且仅当A=n0一】…n__. 证必要性:显然,A必定是边?,a,…,n:的线性序,若存在i,J:1i<J礼, 使得A一-n…0=『…,则根据关系1和引理2.1,s的亏格至少为1,与S是球面矛盾,所 以中边的下标应该是从大到小,从而A=anan…0.充分性显然.I 定义2.2由一个节点和m个自环构成的图叫做环束,记作B.在两个节点之间连结 m(m2)条重边构成的图叫做双极图,记作D. n 一 ?, 章I No.3刘新求等:两类项链图在射影平面上的嵌入605 引理2.9[12]环束点在射影平面上的嵌入个数 (B.肌)=(m 引理2.10双极图D(m2)在射影平面上的嵌入个数 Dm): 证设双极图J[).,n的m条边为a,a2,…0,选择0为图的生成树的边,固定D的 一 个节点1的旋,不失一般性,不妨设节点的旋为ala…n,根据嵌入的联树模型, 则关联曲面S=ala2…am一1A,其中A是al,a2,…0.m一1带上标的线性序. 若关联曲面为射影平面,则a,az,…,n一中必有扭边,且扭边在每个节点处必定连 续.否则,若两条扭边a和at之间还有非扭边a,则a必定与扭边a或a交错,与引理 2.6矛盾.设关联曲面中有条扭边:a,ai+1,ai+2…ai+k一1:1im—k,lm一1, 根据引理2.7和引理2.8,关联曲面 '5f=Alaiai+1ai~2?-?ai+k一1A2A~aiai+1,0+2???i+k一1 aiai+lai+2…ai+k--1aiai+1ai~2'.'ai+k-1 ,N1. 其中A1=ala2?一ai一1,A2:ai+kai+k+l???0m一1,1im一,1m一1. 因为这条扭边有m—k种选择,令=1,2,…,m,1,得到关联曲面共有1+2+3+ … +m一1=型种不同的形式.又因为节点1的旋有(m一1)!种,所以双极图D在 射影平面上的嵌入共有(rn--.1)rn!.I 定义2.3在长为2r+s的圈上,添加r条不相邻的重边和S个自环,且重边和自环均 不相邻,这样的图叫做(,s)型项链图,记作,.特别地,在圈=12…-"的每个 节点添加一个自环得到项链图No;在圈:r"1U2…u2u1上添加n条不相邻的重边得 到项链图'0.把项链图No,的每个自环分别用m个自环代替,而把项链图,o中的每 条添加的重边分别用m条重边代替,所得到的两类图我们分别称之为8和r型项 链图, 分别记作叼和.图1所示分别为图增和图鹏. , 舀|, u., ,, \ 图1图和图; U5U4 一 , 一,, _l_一 /. 0 一 一?.一1l.一一 .00. , ,,.,..一 数学物理VO1.3lA 3主要结论 在图?中,设Ei={n,a…0)(1in)为节点"i处添加的m个自环的边集 合,选择路…札为图?的生成树,令?=ao,将每条余树边切断,设节点i在 生成树的上侧发出的边的带上标的线性序为A,其在生成树的下侧发出的边的带 上标的线 性序为,则联树如图2所示. 图2的联树 A^) ?__ ,% l … —— A 从节点的ao出发,根据各节点的旋按顺时针走遍联树的所有边,依次记录余树边, 则关联曲面 =aoAlA2…J.一A0..' …J…21. 其中c(ao)表示ao的上标. 定理3.1若图J7v的关联曲面为射影平面,则必存在某个J:lJ礼,使得 SnoAjao'..' 证根据前面的引理,若图叼的关联曲面S为射影平面,则有如下断言. 断言1在几个余树边集合E,,…,中,至多有一个含有扭边. 假设在几个余树边集合E,,…,中,至少有两个含有扭边,不妨设其中两个为 ,,且分别含有扭边.;,n,则根据联树中节点,uj的相对位置,关联曲面 一?n;…rz;…o…o 即在关联曲面中,扭边o;和?平行,与引理2.6矛盾. 断言2对任意非扭边a,它所对应的两条半边必定都包含在i或中. 事实上,如果存在非扭边0,它对应的两条半边分别包含在A和五中,则在关联曲面 中非扭边a和ao交错,根据引理2.6,这与关联曲面为射影平面矛盾. 断言3若中不含扭边,则A—Oo或为空,A0o或为空. 因为的边均为非扭边,且根据断言2有对任意a?A,有t一?A,当A不为空 时,显然有^一Op;若P?0,则根据引理2.1,关联曲面s的不可定向亏格大于或等于3, 这与s是射影平面矛盾,所以有A,00.同样当i不为空时有A0o. 根据以上断言,若图』v的关联曲面S为射影平面,则必定存在某个J:1J礼,使 得当i?J时,余树边集Ei(i?J)均不含有扭边,且有A一0o或为空,A,00或为空. 从而关联曲面 Snojn'印j. 定理得证.1 定理3.2图?在射影平面上的嵌入个数 l()=凡l(Bm+1)(go(Bm+1))一一(凡一1)(9o(Bm+1)) , ,, ? ? No.3刘新求等:两类项链图在射影平面上的嵌入607 其中 gO(Bm+)=:, (+)=n2(22m+1一). 证根据定理3.1,若图?的关联曲面为射影平面,则必存在某个J:lJn,使得 余树边集Ei(i?J)均不含有扭边,且关联曲面 s,aoAiao(.oA. noAJn印可看成是边集为a0,01,.2,…,口)的环束B十的关联曲面.由此可知,若 图?的关联曲面为射影平面,且对某个确定的J:1J礼,余树边集Ei(i?J)均不含有 扭边,则EjUao的边在图的关联曲面S中不同的放置方法(均指包含了扭边和非扭边 的选择)对应着环柬B+在射影平面上的嵌入个数 cB十=m2(22m+1一). 另一方面,当i?J时,有i00,五一Oo.不妨设i中含有X1条边,i中含有2 条边,则分别对应着2Xl,2x2条半边.设go(B)表示有X条边的环束在球面上的嵌入个 数,因为i,五是线性序,第一个位置放置不同的半边对应着不同的关联曲面,所以根据引 理2.4和引理2.5,每个余树边集Ei(i?J)的边在图的关联曲面s中不同的放置方法均 为 娶棚c驯=m12m2…,卅 旦22xX11111 .,r, +z2=mr=+1一r=. =二=卯(B+). 综上所述,当余树边集Ei(i?J)中均不含有扭边时,图叼在射影平面上的嵌入个数 为 1(B.,n+1)(夕0(B+1))一. 在上面的嵌入情形中,包含了余树边集含有扭边和不含有扭边两种子情形,分别记 这两种子情形的嵌入个数为(?)和2(?).在不含有扭边的子情形中,a0必为扭 边,且所有余树边集E1,,…,都不含扭边,此时对于1i佗,均有,O0,五一Oo, 所以 ()=(go(Bin+1)). 由对称性,对于所有的J:1Jn,均有 {(A)+(A):1(B+1)(9o(B+1))一. 设图J7v在射影平面上的嵌入个数为l(A),则显然有 ()=?() j=o = ?(()+(叼))一(礼一1)() J=1 :n.Ol(Bm+j)(go(B十1))一一(n一1)(90(B+1))". 608数学物理Vl01.31A 定理得证.I 令m=l,很容易得到以下推论. 推论3.3【9一.】项链图?0在射影平面上的嵌入个数为2一(3n+2). 下面来讨论图在射影平面上的嵌入结构和个数.不失一般性,设重边是加在每对节 点u2一1,u2i(1in)之间.同样选择路乱12…"2作为生成树,令余树边722721=ao,切 断每条余树边,记节点2{一在生成树的上侧发出的边的带上标线性序为,记节点U2i一1 在生成树的下侧发出的边的带上标线性序为,记节点札2i在生成树的上侧发出的边的带 上标线性序为,记节点i在生成树的下侧发出的边的带上标线性序为.则联树如图 3所示. 图3图柳的联树 从节点的n0出发,按照旋走遍联树并依次记录余树边得到图的关联曲面 S=..A1A2AIA2...…1H2...A-2^-1…;-??A-2^-1. 其中c(ao)为ao的上标. 定理3.4若图的关联曲面s为射影平面,则必存在某个J:1Jn,使得 S一.0Ala2..'; 证与定理3.2的证明相类似.若图的关联曲面为射影平面,有如下断言. 断言1在n个余树边集合E,,…,中,至多有一个含有扭边. 断言2若不含扭边,则有A4为空或1n2,Oo,为空或n-t1n-2l,即 A=(A),,=()一. 事实上,对中的任意非扭边.它所对应的两条半边a和o一:若有a?A,则必 定有0t一?A.否则非扭边a必定和ao交错,与引理2.6矛盾.若1n2不为空,则必定 有^一0,若P?0,根据引理2.1,则关联曲面的亏格至少为3.同理有-1-t2Oo或 A - t 1 A-2为空. 根据以上断言,则必存在某个J:1Jn,使得当i?J时,均不含有扭边,且 A为空或1n20o,为空或n-1n-{2一oo.从而图船的关联曲面 S,aoj1j20;. 定理得证.I 定理3.5图在射影平面上的嵌入个数 互l(?)=ngl(D+2)(90(D+2))一一(n一1)(go(D+2)). 其中 1(D+2):(m+2)!, go(D+2)=(m+1)!. No.3刘新求等:两类项链图在射影平面上的嵌入609 证根据定理3.4的证明过程,若图船的关联曲面为射影平面,且对于某个J:1 Jn,余树边集Ei(?J)均不含有扭边时,关联曲面 S—no;n;. 这可以看成是以{0o,0,0;,…,n}为余树边集的双极图J[)+2的关联曲面. 在此种嵌入情形下,Uao在图叼的关联曲面中的放置方法等于双极图D+.在 射影平面上的嵌入个数 1(D+)一(m+2)!. 对于i?J,Ei的边均为非扭边,且有=()一,=()一,即一旦,的边的 放置方法确定,,边的放置方法也唯一确定,故只需考虑余树边集的一组半边在节 点乱1处的放置方法即可.容易得出余树边集在关联曲面中的放置方法均有(m+1)! 种,这即是双极图Dm+2在球面上的嵌入个数go(D+2). 故在上述嵌入情形中,图J7v在射影平面上的嵌入个数为 互1(D+2)(_9o(D+2))"一. 在上面的嵌入情形中,包含了余树边集含有扭边和不含有扭边两种子情形,分别记 这两种子情形在射影平面上的嵌入个数为()和2().在马不含有扭边的子情形 中,ao为扭边,所有余树边集E,E2,…,都不含扭边,此时对于所有的i:1?in,均 有A=(1),,=()一,此子情形的嵌入个数 ()=(go(Din+2)). 由对称性,对于所有的J:1Jl<n,均有 {()+(,?)=gl(D+2)(夕0(J[)+2))一. 设图?在射影平面上的嵌入个数为gl(?),则显然有 (船)一?(船) j=O = ?孵)+(船)]_(礼一1)互(船) j=l =ngi(D+2)(go(D+2))一一(n一1)(g0(D+2)). 定理得证.I 令m=1,立即得到以下推论. 推论3.6【.]项链图?扎.o在射影平面上的嵌入个数为2n(2竹+1). 4结束语 本文中两类项链图在射影平面上的嵌入个数最终都可以归结为两类较为简单的图环束 和双极图在射影平面上和球面上的嵌入个数的计数问题,且这两类图的在结构上有相似之 处,故处理方法和结论亦有相似之处.通过类似的方法我们可以进一步计算这两类项链图 在Klein平面上和其他亏格曲面上的嵌入个数或递推公式,本文作者已经在做这方面的研究 了,得出了一些结论,但最终确定此类图的亏格分布和完全亏格分布或递推公式仍将是比较 艰难的工作. 610数学物理Vl0l_31A 参考文献 … 1GrossJL,FurstML.Hierarchyofimbeddingdistributioninvariantsofgraph.JGraphTheor y,1987,11: 205-220 f2】FurstML,GrossJL,StatemanR.Genusdistributionsfortwoe~assesofgraphs.JCombinThe ory(Ser B),1989,46:22,36 f31GrossJL,RobbinsDP,TuckerTW.Genusdistributionsforbouquetsofcircles.JCombinTheory(Ser B),1989,47:292306 【4]KwakJH,LeeJ.Genuspolynomialsofdippolesofcircles.DisreteMath,1993,33:115— 125 f51TearEH.GenusdistributionsforRingerladders.DiscreteMath,2000,216:235—252 f6]ChenJ,GrossJL,RieperRG.Overlapmarriesandtotalimbeddingdistribution.DiscreteMath,1994, 128:73-94 f7】 KwakJH,ShimSH.Totalembeddingdistributionsforbuquetsofcircles.DisreteMath,2002,248: 93-108 f81刘彦佩.地图的代数原理.北京:高等教育出版社,2006 [9】 ChenYC,LiuYP.Thetotalembeddingdistributionsofcactiandnecklaces.ActaMathSinica(English Seris),2006,22(5):1583—1590 【101杨艳,刘彦佩.两类四正则图的完全亏格分布.数学,2007,50(5):1190-1200 【l1】赵喜梅,刘彦佩.类圈图的亏格分布.数学物理,2008,28(4):757-767 [121Yangyan,YanpeiLiu.Flexibilityofembeddingsofbouquetsofcirclesontheprojectiveplaneandklein bottle.ElectronicJournalofCombinatorics,2007,14(1):R80 NumbersofEmbeddingsofTwoTypesofRegularGraphs ontheProjectivePlane LiuXinqiuHuangYuanqiuWangJingOuyangZhangdong (CollegeofMathematicsandComputerScience,HunanNormalUniversity,Changsha410081) Abstract:Embeddingnumbersofgraphsondistinctgenussurfacesarealwaysrelated.There— foreanalyzingembeddingnumbersofgraphsonlowergenussurfacesisimportanttodetermine theirgenusdistributionsandtheirtotalgenusdistributions.Basedonthemodelofjointtree introducedbyProfessorLiu,thispapercalculatestheembeddingnumbersoftwotypesof necklacegraphsontheprojectiveplane. Keywords:Surface;Genus;Embedding;Jointtree. MR(2000)SubjectClassification:05C10