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

（河北工业大学理学院，天津 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的嵌入与关联曲面之间存在一一对应关系．

由曲面的层分割，与同一个顶点……