3-正则图的最大亏格计算公式

A Formula for computing of Maximum Genus of a 3-Regular Graph

本文主要讨论了三正则连通图的叶子数l(T)以及叶子数与图的最大亏格γM之间的关系,并给出了3-正则图的最大亏格的计算公式:γM=12(l(T)+pα-pβ);这里,T是图G的XUONG树,l(T)是T的叶子数;pα,pβ分别是G-T的偶长路数和奇长圈数.作为应用我们计算了若干类图的最大亏格.

In this paper we discuss the relations between the number of XUONG tree＇s leaf l（T） and the maxigenus and give a formulae of computing maximum genus of a 3 - regular graph： γM = 1/2（ l（T） ＋ pα - pβ）, mum T is a XUONG tree of a graph, l（T） is the number of leaf of T,pα is the number of odd - length - circle of G - T, pβ is the number ofeven - length - circle of G - T . As application , we compute the maximum genus of several kinds of graphs.