4-连通图中圈上的可去边和可收缩边

给出某些4 连通图中圈上的可收缩边和可去边的分布情况,得到如下结果:最小度至少为4或围长至少为5的4 连通图,其任一圈上至少有两条可去边;对4 连通图中的某些最长圈上至少有两条可收缩边.

λK_v分解为一个二部图

λKv是λ重v点完全图,对于有限简单图G,所谓图设计GGDλ(v)是序偶(X,B),其中X是Kv的顶点集,而区组集B为λKv的全部边的1种分拆,其中每个成员(区组)都是与G同构的子图.利用"差方法"、"带洞图设计"等工具,结合一系列小设计的构作,对1个6点8边图G1的图设计进行了讨论,并证明了:存在G1GDλ(v) λv(v-1)≡0(mod16),v≥6.

关于图的s-可迹性的一个新结果

利用图G的部分平方图的独立集Ik + 1(G )的邻域交与LTW 序列 ,得到了关于G的s 可迹性的一个新结果 .

跳跃图是H-图的一个充分条件

图G的跳跃图记作J(G) .若G是H 图且 p(G)≥ 7,q(G)≥ 2 p - 2 ,则J(G)是H 图 ,从而证明G .Chartrand等文中提出的猜想B是正确的 .

8长圈加1条弦的图设计

设λKv是λ重v点完全图 ,G是无孤立点的有限简单图 .将G设计记作 (v ,G ,λ)GD=(X ,B) ,其中X是完全图Kv 的顶点集 ,B是Kv 中同构于G的子图 (区组 )的集合 ,使得Kv 中每条边恰好出现在B的λ个区组中 .利用差分法、拟群及组合设计理论中经典的PBD方法等 ,建立了若干有效的构造图设计的递归方法 ,并给出了若干小设计的直接构造 .最终解决了λ=1时 ,8长圈加 1条弦的图设计的存在性问题 ,并给出其λ

联图和结合图的Menger性质

对两个给定的图G和H ,以G +H表示G和H的联 ,以G[H]表示G对图H的结合图 ,证明了如下结果 :(1)G +H是Menger图当且仅当G和H均为Menger图 ;(2 )若G和H均为Menger图 ,且G的任一导出子图也是Menger图 ,则G[H]必为Menger图 .

6长圈加1条弦的图设计

设λK_v是λ重v点完全图,G是无孤立点的有限简单图.将G-设计记作(v,G,λ)-GD,是指一个序偶(X,),其中X是完全图K_v的顶点集,是K_v中同构于G的子图(区组)的集合,使得K_v中每条边恰好出现在的λ个区组中.解决了图6长圈加1条弦的图设计问题,并给出其λ=1时的存在谱.

赋权图中重路的隐赋权度条件

对 2 -连通非Hamilton赋权图G ,本文给出了重路存在的隐赋权度条件 :若G满足文中描述的条件C1 、C2 ,且max{idw(u) ,idw(v) |d(u ,v) =2 }≥ m2 ,则当G中存在y -最长路时 ,存在一最重的y-最长路P(x ,y)满足dw(x)≥ m2 .

B.D.Acharya和S.M.Hegde关于算术图一个猜想的证明

B.D.Acharya和S.M.Hegde猜想[1]:(1)、如果圈C_(4t+1)是(k,d)的算术图,那么必有k=2td+2r,其中r是某个非负整数;(2)如果圈C_(4t+3)是(k,d)算术图,则k=(2t+1)d+2r,其中r是某个非负整数。本文对以上猜想给出了肯定性证明。

3维格P_(n1)×P_(n2)×P_(n3)和台阶图的控制满划分

通过给出3维格P_(n1)×P_(n2)×P_(n3)和台阶图S^((m))_(n_1、n_2、n_3)的控制满划分，证明了控制划分数d（P_(n1)×P_(n2)×P_(n3)）=4，d（SS^((m))_(n_1、n_2、n_3)）=4（其中ni≥2，i=1，2，3；m≥1）.

Mycielski图的L(2,1)-标号

设μ(G)表示一个图G的Mycielski图,λ(G)为G的L(2,1) 标号数.给出了λ(μ(G))的上、下界和λ(μ(G))达到下界(|G|+1)的一个充分条件.

一个图的图设计(Ⅰ)

λKv是λ重v点完全图.对于有限简单图G,所谓的图设计GGDλ(v)是一个序偶(X,B),其中X是Kv的顶点集,而区组集B为λKv的全部边的一种分拆,其每个成员(区组)都是与G同构的子图.运用"差方法"、"带洞图设计"等工具,结合一系列小设计的构作,对一个6点9边图H的图设计进行了讨论,并证明了:存在HGD(v) v≡0,1(mod9)且v≠9.

高度图的全色数

证明了 :如果图G的最大度顶点数r(G)满足r(G) ≤｜V(G) ｜-Δ(G) - 1,且δ(G) +2Δ(G)≥ 52 ｜V(G)｜+32 .则G的全色数xT(G) =Δ(G) +1.

s-Hamilton-连通图的一个充分条件

证明了下面的结论 :设G是n阶 (k+2 +s) 连通图 ,G 为G的部分平方图 ,k≥ 2 ,而 (a1,a2 ,… ,ak+ 1)是k LTW序列 .若对于每个X ∈Ik+ 1(G ) ,在G中有 k+ 1i=1aisi(X) >n +s,则G是s Hamilton

3连通图的可去边的分布

e是 3连通图 G的一条边 ,如果 G-e是某个 3连通图的剖分 ,则称 e是 G的可去边 .研究了 3连通图的可去边的分布规律 ,得到 :1设 C是阶至少为 6的 3连通图 G中的一个圈 ,如果 C上不存在 3个连续的 3度点 ,那么 C上至少有两条可去边 .2设 T是阶至少为 5的 3连通图 G的一棵生成树 ,如果 G中至多存在一个极大半轮 ,那么 T上至少有一条可去边 .由此可得 :阶至少为 5的 3连通 3正则图的生成树上至少有一条可去边 .

关于(g,f)-2-覆盖图

一个图G称为 (g ,f) 2 覆盖图 ,如果G的任何两边都属于它的一个 (g ,f) 因子。给出了当g <f时一个图是 (g ,f) 2 覆盖图的一个充分必要条件 ,并由此得到了若干相应新结果。

关于(g,f)-3-消去图

一个图G称为一个 (g ,f) 3 消去图 ,如果G的任何三条边不属于它的一个 (g ,f) 因子。给出了当 g <f时一个图是 (g ,f) 3 消去图的一个充要条件 ,并得到了若干相应新结果。

关于图的分支因子

给出图Ｇ是｛Ｐ２，Ｃｉ｜ｉ≥３｝—消去图的一个充要条件及Ｇ是｛Ｐ２。

图的圆色数等于其色数的充分条件

图G的圆色数xc(G) (也称为星色数 )是图的色数的一种推广 .给出了图的圆色数等于其色数的一些充分条件 .

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

设G是一个二分的(mg+k,mf-k) 图,其中1≤k<m,g(x)和f(x)是定义在V(G)上的整数值函数,且 x∈V(G)有r2≤g(x)<f(x),H1,H2,…,Hr是G的r个顶点不相交的子图,且E(Hi)=k(1≤i≤r).本文证明了G存在一个子图R,使得R有(g,f) 因子分解与Hi正交(1≤i≤r).