6-齐次二分图的围长

研究6-齐次二分图的直径和围长之间的关系及围长的界,利用距离正则图的性质及其交叉表,证明了度数大于2的一类6-齐次二分图的围长不超过12．     

8-齐次二分图的围长

证明了当d≠r 2,r 3时,度数大于2的8齐次二分图的围长不超过16.     

一类围长为3的单圈图的加边问题

用F(U3,n-2,1)表示围长为3、顶点数为n的单圈添加1条边后其变更图的最小直径.本文证明了当n为偶数时,其最小直径为n/2-1;当n为奇数时,其最小直径为「n/2」.该结论改进了已有结果,为进一步研究奠定了基础.     

二分图上有限制条件的(g,f)-因子分解

设G=(X,Y,E)是二分图,g,f是定义在V(G)上的正整数值函数,且对任意的x∈V(G)有g(x)＜f(x).令G是(mg,mf-1)-图,证明了:①若,g(x)≥1,H是G的任一含有m条边的子图.则G有一个(g,,)-因子分解与H-正交.②若g(x)≥2,H是G的任一含有2m条边的子图,则G有一个(g,f)-因子分解与H2-正交.     

二分图上有限制条件的(g,f) 因子和f 因子

设图G=(X,Y,E)是二分图, g,f是定义在V(G)上的正整值函数, 且对任意的x∈V(G)有g(x)＜f(x), 证明了: 如果图G是(mg,mf-1)-图, M是G的任一含有m条边的对集, 则存在图G的一个(g,f)-因子F, 使F包含M任意给定的一条边, 并且不包含其他的m-1条边; 二分图G是(2m-1)-边连通的(mf)-图, 则图G有一个f-因子包含任意给定的一条边, 并且不包含任意其他的m-1条边.     

围长至少为6的曲面图的列表单射染色

图G的一个点染色称为单射染色,如果任何两个有公共邻点的顶点染不同的颜色.一个图G称为单射k-可选择的,如果对于顶点V(G)的任何一个大小为k的允许颜色列表L,都存在一个单射染色φ,使得对于v∈V(G),有φ(v)∈L(v).使得G为单射k-可选择的最小k,称为G的列表单射染色数,记作χ_i~l(G).设G是最大度为Δ,围长为g的可嵌入到欧拉示性数χ(Σ)≥0的曲面Σ的一个图.证明了若Δ≥7且g≥6,则χ_i~l(G)≤Δ+3.     

具有围长对（g,h）的3——正则图

一个具有围长对(g,h)的k—正则图称为(k;g,h)一图,这种图的最小可能顶点数记作f(k;g,h). 本文证明了:f(3;5,8)=18,f(3;6,7)=18,f(3;7,8)=24,2/3(7S+4)≤f(3;6,2S+l)≤6S+4,k≥3;部分地回答了F·Harary在文[1]中提出的问题.     

二分图上有限制条件的(g,f)-因子和f-因子

设图G=(X,Y,E)是二分图,g,f是定义在V(G)上的正整值函数,且对任意的x∈V(G)有g(x)＜f(x),证明了:如果图G是(mg,mf-1)-图,M是G的任一含有m条边的对集,则存在图G的一个(g,f)-因子F,使F包含M任意给定的一条边,并且不包含其他的m-1条边;二分图G是(2m-1)-边连通的(mf)-图,则图G有一个f-因子包含任意给定的一条边,并且不包含任意其他的m-1条边.     

图的围长与k-联性

联性是图的一个重要的连通性质,Kawarabayashi证明了对k≠4,5,围长至少为11的2k-连通图是k-联图．本文对该结果进行了改进,证明了对k≥12,围长为9,或7≤k≤11,围长至少为10的2k-连通图是k-联图．     

直径为3的GS图

研究了直径为３的ＧＳ图的性质。提出了一个非Ｉ－ＧＳ图的构造方法，并证明了由此方法可构造出无穷多个非Ｉ－ＧＳ图，从而解决了Ｐｈｉｌｉｐ　Ｌａｕｆｅｒ提出的下列两个问题：（１）除了已知的两个非Ｉ－ＧＳ图，是否还有其他非Ｉ－ＧＳ图；（２）非Ｉ－ＧＳ图是否为有限个。     

二分图中具有正交(g,f)-因子分解的子图

设G是一个二分的(mg+k,mf-k) 图,其中1≤k相似文献   

均衡二分图中存在哈密顿因子的条件

研究了在均衡二分图中包含给定哈密顿圈的[k,k+1]因子的存在性问题.根据图论中因子和临界图理论,并结合代数知识,针对均衡二分图,研究图的阶数,顶点的度和因子之间的关系,分情况讨论,通过对均衡二分图的临界条件的限制,给出均衡二分图中存在包含给定的哈密顿圈的[k,k+1]因子的充分条件.该条件在很大程度上改进了已有的包含哈密顿圈的度条件,进一步完善了包含哈密顿圈的因子理论.算例表明所用方法的有效性,所得结论的正确性.     

一类直径为3的2-连通图的最大亏格

用ξ(G)表示图G的Betti亏数，ζ(G)表示图G的衰变数，本文在文献[5]图的结构上增加点和边得到一类直径为3的2-连通类极图(即m=2n-5)．通过计算此类图的ξ(G’)和ζ(G’)的范围，得到了它们的最大亏格。     

Bipartite Graphs with the First and Second Largest Laplacian Spectral Radius

LetBkn be the class of bipartite graphs with n vertices and k cut edges.The extremal graphs with the firt and the second largest Laplacian spectral radius among all graphs in Bkn are presented.The bounds of the Laplacian spectral radius of these extremal graphs are also obtained.     

关于2连通图的容错直径与宽直径的注记

在实时系统中,容错直径和宽直径是两个度量网络信息传输延迟和性能的重要参数.对于一般的图G,确定它的容错直径Dk困难很大,而确定它的宽直径dk却是个NPC问题,因此讨论它们之间的关系显得很重要.该文讨论了2连通图的容错直径与宽直径之间的一些性质,给出若G是直径为2的2连通图,则d2=D2+1的充要条件为存在两顶点u、v∈V(G),其中uv∈E(G),使得L(G)=L(G;u,v)=4或5.