邵澤玲，張相梅，李志國(guó)，王金環(huán)

（河北工業(yè)大學(xué)理學(xué)院，天津 300401）

完全二部圖最小虧格嵌入的數(shù)目

邵澤玲，張相梅，李志國(guó)，王金環(huán)

（河北工業(yè)大學(xué)理學(xué)院，天津 300401）

圖在曲面上的可嵌入性是拓?fù)鋱D論的主要問(wèn)題之一．在劉彥佩提出的聯(lián)樹(shù)模型的基礎(chǔ)上，通過(guò)一個(gè)圖在曲面上的嵌入可用其聯(lián)樹(shù)，進(jìn)一步其關(guān)聯(lián)曲面來(lái)表示，然后逐層分段，得到了完全二部圖Km,n至少有個(gè)不同的最小虧格嵌入，其中常量C1，C2，C3，C4，C5和C6依賴(lài)于m模4和n模4的余數(shù)．此結(jié)論改進(jìn)了文獻(xiàn)[8]中結(jié)果．

可定向嵌入；最小虧格；聯(lián)樹(shù)；可定向曲面；曲面

曲面是無(wú)邊緣的2-維緊流形，嵌入是指圖在曲面上的可定向胞腔嵌入．圖G的虧格G是指G所能可定向嵌入曲面的最小虧格．確定圖的最小虧格問(wèn)題已被Thomassen[1]證明是NP-完備的．其中完全圖的解決就經(jīng)歷了一個(gè)漫長(zhǎng)的過(guò)程，且由此產(chǎn)生了現(xiàn)代拓?fù)鋱D論．目前已知結(jié)果皆涉及有一定對(duì)稱(chēng)性的特定圖類(lèi)，且鮮有考慮計(jì)算最小虧格嵌入數(shù)目的問(wèn)題．完全圖及完全二部圖的嵌入數(shù)目問(wèn)題的解決見(jiàn)文獻(xiàn)[2-6]．2003年，劉彥佩[7]提出了圖的聯(lián)樹(shù)模型，建立了圖的聯(lián)樹(shù)與嵌入的對(duì)應(yīng)關(guān)系，為求圖的虧格嵌入等問(wèn)題提出了更有效的工具．本文在聯(lián)樹(shù)模型的基礎(chǔ)上，改進(jìn)了文獻(xiàn)[8]中結(jié)果，得到完全二部圖Km,n至少有個(gè)不同的最小虧格嵌入，其中，常量C1，C2，C3， C4，C5和C6依賴(lài)于m模4和n模4的余數(shù)．

1 預(yù)備知識(shí)

定理1[7]給定圖G的一支撐樹(shù)，則圖G的嵌入與關(guān)聯(lián)曲面之間存在一一對(duì)應(yīng)關(guān)系．

由曲面的層分割，與同一個(gè)頂點(diǎn)關(guān)聯(lián)的半邊構(gòu)成一個(gè)層段，關(guān)聯(lián)曲面可被逐層分段，則調(diào)位是定義在層分割上交換同一層段內(nèi)元素位置的一種運(yùn)算，用符號(hào)A B表示A經(jīng)過(guò)調(diào)位得到B．為方便起見(jiàn)，用尖括號(hào)標(biāo)注內(nèi)部任兩元素可交換前后位置．

2 主要結(jié)果

[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]劉彥佩．組合地圖進(jìn)階[M]．北京：北京交通大學(xué)出版社，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．

[責(zé)任編輯 楊屹]

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

國(guó)家自然科學(xué)基金（11301135，61203142）；河北省自然科學(xué)基金（A2012202067，F(xiàn)2014202206）

邵澤玲（1977-），女（漢族），講師，博士．