完全二部图最小亏格嵌入的数目

邵泽玲，张相梅，李志国，王金环

（河北工业大学理学院，天津 300401）

完全二部图最小亏格嵌入的数目

邵泽玲，张相梅，李志国，王金环

（河北工业大学理学院，天津 300401）

图在曲面上的可嵌入性是拓扑图论的主要问题之一．在刘彦佩提出的联树模型的基础上，通过一个图在曲面上的嵌入可用其联树，进一步其关联曲面来表示，然后逐层分段，得到了完全二部图Km,n至少有个不同的最小亏格嵌入，其中常量C1，C2，C3，C4，C5和C6依赖于m模4和n模4的余数．此结论改进了文献[8]中结果．

可定向嵌入；最小亏格；联树；可定向曲面；曲面

曲面是无边缘的2-维紧流形，嵌入是指图在曲面上的可定向胞腔嵌入．图G的亏格G是指G所能可定向嵌入曲面的最小亏格．确定图的最小亏格问题已被Thomassen[1]证明是NP-完备的．其中完全图的解决就经历了一个漫长的过程，且由此产生了现代拓扑图论．目前已知结果皆涉及有一定对称性的特定图类，且鲜有考虑计算最小亏格嵌入数目的问题．完全图及完全二部图的嵌入数目问题的解决见文献[2-6]．2003年，刘彦佩[7]提出了图的联树模型，建立了图的联树与嵌入的对应关系，为求图的亏格嵌入等问题提出了更有效的工具．本文在联树模型的基础上，改进了文献[8]中结果，得到完全二部图Km,n至少有个不同的最小亏格嵌入，其中，常量C1，C2，C3， C4，C5和C6依赖于m模4和n模4的余数．

1 预备知识

定理1[7]给定图G的一支撑树，则图G的嵌入与关联曲面之间存在一一对应关系．

由曲面的层分割，与同一个顶点关联的半边构成一个层段，关联曲面可被逐层分段，则调位是定义在层分割上交换同一层段内元素位置的一种运算，用符号A B表示A经过调位得到B．为方便起见，用尖括号标注内部任两元素可交换前后位置．

2 主要结果

[1]Thomassen C．The graph genusproblem is NP-complete[J]．JAlgorithms，1989，10：68-576．

[2]Korzhik V，VossH J．Exponentially fam iliesofnonisomorphicnontriangularorientablegenusembeddingsofcomp letegraphs[J]．JCombin Theory Ser B，2002，86：186-211．

[3]Korzhik V，VossH J．On thenumbernonisomorphicorientableregularembeddingsof completegraphs[J]．JCombin Theory SerB，2001，81：58-76．

[4]Law rencenko S，NegamiS，White A T．Three nonisomorphic triangulationsof an Orientable surfacew ith thesame complete graph[J]．Discrete M ath，1994，135：367-369．

[5]Lins S．A sequence representation formaps[J]．DiscreteMath，1980，30：249-263．

[6]Ren H，Bai Y．Exponentially many maximum genus embeddings and genus embeddings for complete graphs[J]．Science in China，2008，51（11）：2013-2019．

[7]刘彦佩．组合地图进阶[M]．北京：北京交通大学出版社，2003．

[8]Shao Z L，Liu Y P，LiZG．On thenumberofgenusembeddingsof completebipartitegraphs[J]．Graph Combin，2013，29（6）：1909-1919．

[9]Liu Y P．Embeddability in Graphs[M]．Boston：K luw er，1995．

[责任编辑 杨屹]

On thenumberof genusembeddingsof completebipartite graphs

SHAO Ze-ling，ZHANG Xiang-mei，LIZhi-guo，WANG Ji-huan

(Schoolof Science,HebeiUniversity of Technology,Tianjin 300401,China)

The embeddability of a graph on a surface isone ofmajorproblems in topologicalgraph theory.Based on the joint trees,an embedding of a graph on a surface can be represented by a joint tree,further by an associated surface of it. By dividing the associated surfaces into segments layerby layer,the number ofgenusembeddingsof a complete bipartite graph Km,nis derived,namely,where C1,C2,C3,C4,C5and C6are constants depending on the residual classof m modular4 and thatof n modular 4.

orientable embedding;m inimum genus;joint tree;orientable surface;surface

O157.5

A

1007-2373(2014)04-0076-04

2013-11-10

国家自然科学基金（11301135，61203142）；河北省自然科学基金（A2012202067，F2014202206）

邵泽玲（1977-），女（汉族），讲师，博士．