关于图的余树的奇连通分支数的内插定理  

AN INTERPOLATION THEOREM ON THE NUMBER OF ODD COMPONENTS OF CO-TREES

作　　者：任韩[1] 吕长青[1] 马登举[1] 卢俊杰[1] 

机构地区：[1]华东师范大学数学系,上海200062

出　　处：《应用数学学报》2005年第3期546-550,共5页Acta Mathematicae Applicatae Sinica

基　　金：国家自然科学基金(10271048号)资助项目;上海市重点学科基金;上海市科委重点学科基金项目资助(批准号:04JC14031)

摘　　要：本文研究了连通图的余树的奇连通分支数与其可定向嵌入的关系.我们先给出了关于连通图的余树的奇连通分支数的内插定理.作为其应用,我们推广了Xuong和刘彦佩关于图的最大亏格的计算公式,并且证明了如下结果:任意一个连通图G一定满足下列条件之一: (a)对于任意的满足γ(G)≤g≤γM(G)整数g,只要图G嵌入到可定向曲面Sg上,就存在支撑树T,使g-1/2β(G)-ω(T)),其中,γ(G)与γM(G)分别是图G的最小和最大亏格,β(G)与ω(T)分别是图G的Betti数和由T确定的余树的奇连通分支数; (b)对连通图G的任意一个支撑树T,G可以嵌入某个可定向曲面上使其恰好有ω(T)+1个面.特别地,我们给出了所有非平面的3-正则的Hamilton图G所嵌入的可定向曲面的亏格的计算公式.This paper investigates the relation between the number of odd components of co-trees in a connected graph G and its orientable embeddings. Firstly, it gives an interpolation theorem on the number of odd components of co-trees in a connected graph.Secondly, it proves that for any connected graph G, it must satisfy one of the following two conditions： （a） for every integer g with γ（G）≤g≤γM（G）,there exists a spanning tree T of G with ω（T） odd components such that g=1/2（β（G）-ω（T））, where γ（G） and γM（G） are, respectively, the minimum and maximum genus of G, and β（G） and ω（T）are, respectively, the Betti number of G and the number of odd components of co-trees determined by T; （b） for every spanning tree T with ω（T） odd components, G may be embedded into some orientable surface such that there are exactly ω（T） ＋ 1 faces. This extends a famous result for maximum genus of Xuong and Liu.As an application,the paper provides a formula to calculate the genus g of an orientable surfaces S（g） into which a nonplanar 3-regular Hamiltonian graph may be embedded.

关 键 词：图的余树的奇连通分支数 图的亏格 

分 类 号：O157.8[理学—数学]