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

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

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

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

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

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

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

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

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

1 預(yù)備知識

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

由曲面的層分割，與同一個頂點關(guān)聯(lián)的半邊構(gòu)成一個層段，關(guān)聯(lián)曲面可被逐層分段，則調(diào)位是定義在層分割上交換同一層段內(nèi)元素位置的一種運算，用符號A B表示A經(jīng)過調(diào)位得到B．為方便起見，用尖括號標注內(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]劉彥佩．組合地圖進階[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．

[責任編輯 楊屹]

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

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

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