图的生成树, 基本圈与Betti亏数

G为图且T是G的一棵生成树. 记号ξ(G, T)表示G＼E(T)中边数为奇数的连通分支个数. 文献［2］称ξ(G)=min[DD(X]T[DD)]ξ(G, T)为图G的Betti亏数, 这里min取遍G的所有生成树T. 由文献［2］知, 确定一个图G的最大亏格主要确定这个图的Betii亏数ξ(G).该文研究与Betti亏数有关的图的特征结构, 得到了关于图的最大亏格的若干结果.     

直径为4的图的最大亏格

本文证明了如下结果:设G是直径为4的简单囹,若G不含3阶完全子图K3,则G的Betti亏数ξ(G)≤2,因此有G的最大亏格γM(G)≥1/2β(G)-1.而且,在这种意义下,所得到的界是最好的.     

与直径和围长有关的图的最大亏格

利用图的直径和围长来研究图的最大亏格的下界,得到了如下结果：设G是直径为d的简单图,若G的围长不小于d（其中d为不小于3的整数）,则ξ（G）≤2,即γM（G）≥1/2β（G）-1．而且,在这种意义下,所得到的界是最好的．     

图的最大亏格、支配数和围长

一个连图G的最大亏格γM（G）=（β（G）-ξ（G）/2,其中β（G）=E（G）-V（G 1是G的圈秩,ξ（G）是G的Betti亏数,本文利用G的支配数和围长给出了G的Betti亏数ξ（G）的一个上界,从而也给出了最大亏格γ（M（G）的一个下界,而且它是可达的,对于某些图类,该下界比黄元秋（2000）所给下界更好。     

与直径和围长有关的最大亏格的下界

本文证明了如下结果:设G为直径为d的简单图,若G的围长不小于d,则当d为不小于4的偶数时,有ξ(G)≤1,即G是上可嵌入的;当d为不小于3的奇数时,有ξ(G)≤2,即γM(G)≥1/2β(G)-1.     

图的最大亏格与图的顶点划分

本文研究了图的Betti亏数与图的顶点划分的导出子图之间的关系,得到了图的最大亏格上界由其顶点划分的导出子图所表达的关系式,由此给出了图的最大亏格的一些新结果．     

与直径和围长有关的最大亏格的下界的一个注记

改正了文章"与直径和围长有关的最大亏格的下界(数学学报2004,47(6):1201-1204)"中的一个错误结论,并得到了如下结果:设G是直径为d(G)的简单图,若G的围长g(G)■d(G),则ξ(G)■2,从而γM(G)■(1/2)β(G)-1.     

图的最大亏格与图的着色数

结合边连通性,本文给出了一个图的Ｂｅｔｔｉ亏数由这个图的补图的着色数所确定的上界式,证明了所给出的上界式是最好的,得到关于图的最大亏格下界的若干新结果．     

关于图的最大亏格的下界

主要考虑2-边和3-边连通图的最大亏格下界情形,推广了J.Chen等(1996)的主要结果,证明了     

关于嵌入图的最大亏格

不依赖图的其它参数, 而主要依据图嵌入在定向曲面上的有关嵌入性质, 该文研究图的最大亏格.     

图的限制性边连通度等于其最小边度的一个充分条件

设G是有限简单无向图．D,g和δ分别表示G的直径,围长和顶点最小度,本文证明,如果D≤g-2,且δ≥3,那么λ＇＝ξ,这里λ＇＝λ＇（G）和ξ＝ξ（G）分别表示G的限制性边连通度和最小边度,它在条件和结论两个方面都改进了已有的研究结果。     

ON k-DIAMETER OF k-CONNECTED GRAPHS

Abstract. Let G be a k-connected simple graph with order n. The k-diameter, combining con-nectivity with diameter, of G is the minimum integer     

一类3-连通图的上可嵌入性

结合图的k-边形2-因子条件,确定了一类上可嵌入的3-连通图。     

关于直径为４的图的最大亏格

该文证明了如下结果：设犌为直径为４的简单图,若犌不含３阶完全子图犓３,则犌的Ｂｅｔｔｉ亏数ξ（犌）≤４,因此有犌的最大亏格γ犕（犌）≥ １２β（犌）－２．     

图的上可嵌入性的邻域条件

用NG（u）表示一个图G中任意点u的邻域集．本文主要证明了下述结果：设G是无环图,对G中任意相邻的点u和υ,即uυ∈E（G）,若如下两条件之一满足：（1）|NG(u)∩NG(υ)≥2;（2）G是2-点连通的图,且|NG(u)∩NG(υ)|≥1,则G是上可嵌入的．     

REFINED CONNECTIVITY PROPERTIES OF ABELIAN CAYLEY GRAPHS

1.IntroductionAgraphG=(V,E)meansafinitegraphwithoutloopsandmultipleedgeswithvertexsetVandedgesetE,theclassicaledgeconnectivityA(G)ofGistheminimumsizeofasetUofedgessuchthatG--Uisdisconnected,andsuchasetUiscalledaoutsetofG.Notethatintheabovedefinition,absolutelynoconditionsorrestrictionsareimposedeitheronthecomponelltsofG--UoronthesetU.ThusitwouldseemnaturaltogeneralizetheconceptofedgeconnectivitybyintroducingsomeconditionsorrestrictionsonthecomponentsofG--Uand/orthesetU.Asageneralizatio…     

ON f-EDGE COVER-COLOURING OF SIMPLE GRAPHS

An f-edge cover-colouring of a graph G = (V, E) is an assignment of colours to the edges of G such that every colour appears at each vertex υ∈ V at least f(υ) times.The maximum number of colours needed to f-edge cover colour G is called the f-edge cover chromatic index of G, denoted by χfc(G). This paper gives that min[d(ν)-1/f(ν)] ≤χfc(G) ≤min[d(υ)/f(υ)].