邻域并和[A,B]—覆盖图

设ａ≤ｂ是整数，Ｇ＝（Ｖ（Ｇ），Ｅ（Ｇ）是一个图。Ｇ的一个支撑子图Ｆ称为Ｇ的一个［ａ，ｂ］－因子，若对任意的υ∈Ｖ（Ｇ）有ａ≤ｄＦ（υ）≤ｂ，图Ｇ称为是［ａ，ｂ］－覆盖图，若对Ｇ的每一条边，存在Ｇ的一个［ａ，ｂ］－因子包含它。本文给出了一个图的［ａ，ｂ］－覆盖图的关于领域并的充分条件，得到了下列结果：设１≤ａ〈ｂ是整数，Ｇ是一个阶为ｎ的图，最小度δ（Ｇ）≥α且ｎ≥２（ａ＋ｂ）（ａ＋ｂ－１）１／ｂ如     

关于图的圈覆盖

Ａ．Ｉｔａｌ和Ｍ．Ｒｏｄｅｈ给出了两个关于图的圈覆盖的猜想：（ｉ）任意２－边连通图Ｇ＝（Ｖ，Ｅ）有困覆盖Ｃ，使ｌ（Ｃ）≤｜Ｅ｜＋｜Ｖ｜－１；（ｎ）任意２－边连通图有困覆盖，使图的每条边至多被覆盖两次．本文证明了猜想对平面图和２－边连通没有３－边割的图成立，并给出了一与两猜想等价的条件．同时也对著名的２－圈覆盖猜想作了讨论．     

小圈二重覆盖三角剖分图

近三角剖分图是一连通平面图,其内面均为三角形,而其外面可能不是．图Ｇ的一个二重覆盖（ＣＤＣ）指它的一个圈族Ｃ,使得Ｇ的每条边恰属于Ｃ的两个元素．令Ｇ为一个具有ｎ个节点的２－连通平面图,Ｃ为Ｇ的一个ＣＤＣ．若｜Ｃ｜≤ｎ－１,则称Ｃ为Ｇ的一个小圈二重覆盖（ＳＣＤＣ）．本文证明每个近三角剖分图均存在一个ＳＣＤＣ．     

关于Faudree定理的一个注记

假定Ｇ是顶点数的ｎ的２－连通图，Ｇ中顶点数为４且包含爪Ｋ１．３的子图称为爪型子图。本文证明了对Ｇ的任一爪型图Ｆ，任何ｕ，ｖ属于Ｖ（Ｆ），由距离ｄ（ｕ，ｖ）＝２＝│Ｎ（ｕ）ＵＮ（ｖ）│≥２ｎ－１／３，则Ｇ是哈密顿图。     

关于不含长导出路的图的一个注记(英文)

一个不含具有ｔ个顶点的导出路的图被称为是Ｐｔ－自由的．一个连通图Ｇ的ｉ－中心是由Ｖ（Ｇ）中所有距其它任何顶点的距离不大于ｉ的顶点组成的集合．对于Ｖ（Ｇ）的两个子集Ｓ和Ｔ,如果对任何ｘ∈Ｔ都有ｙ∈Ｓ,使得ｘ距ｙ的距离不大于ｄ,则称Ｓｄ－支配Ｔ．本文解决了由Ｏ．Ｆａｖａｒｏｎ和Ｊ．Ｌ．Ｆｏｕｑｕｅｔ提出的一个公开问题,即证明了如下结果：对任何Ｐｔ－自由图Ｇ,如果ｉ｜ｔ／２｜且ｐ１,则Ｃｉ（Ｇ）（ｐ＋１）－支配Ｃｉ＋ｐ．     

一类OF图及其泛连通性

设Ｇ为ｎ阶连通图，且对Ｇ中任一对距离为２的顶点ｕ、ｖ，有ｄ（ｕ）＋ｄ（ｖ）≥ｎ，则称Ｇ为ＯＦ图．本文讨论了ＯＦ图的泛连通性，主要得到下列结果：设Ｇ为ｎ阶ＯＦ图，则Ｇ为下列三类图之一：（１）Ｇ是［５ｎ］－泛连通图（２）Ｈ＋；（３）Ｋｍ＃Ｋｎ－ｍ＋２及其部分支撑子图，其中３≤ｍ≤ｎ－１，｜Ｖ（Ｈ）｜＝．     

K1,n—free图的f—因子

图Ｇ称为Ｋ１,ｎ－ｆｒｅｅ,若图Ｇ不包含同构于Ｋ１,ｎ的导出子图。设ｆ（ｘ）是定义在Ｖ（Ｇ）上的非负整数函数,Ｇ的一个支撑子图Ｆ称为Ｇ的一个ｆ－因子,若对任意的ｖ∈Ｖ（Ｇ）有ｄＦ（ｖ）＝ｆ（ｖ）,对Ｋ１,ｎ－ｆｒｅｅ图存在ｆ－因子涉及到最小度条件进行了研究,得到了一个充分条件。有关定理为本定理的特例。     

双循环，对集和树

令Ｇ＝（Ｖ，Ｅ）为一个图，它的节点数为ｎ，不仅是一个双循环也是一个上循环．记β（Ｇ）为Ｇ的双循环空间的维数．对于Ｇ的一个子图Ｈ，用φ（Ｇ，Ｈ）表示Ｇ的支撑森数目，使得它的每个树均恰含Ｈ的一条边．图Ｇ的Ｈ扩张Ｘ（Ｇ，Ｈ）在Ｇ上增添一个新节点ν，连ν与Ｈ的每一个奇次节点以一边所得到的图．本文证明，φ（Ｇ，Ｈ）是个偶数，要么Ｘ（Ｇ，Ｈ）不连通，要么Ｘ（Ｇ，Ｈ）有一个非零双循环．对于一个欧拉图Ｇ，令λ（Ｇ）为Ｇ中这样边的最小数目，使得在将它们从Ｇ中收缩掉而得到的图Ｇ中，所有那些落在奇数个完满对集上的边，形成一个非零双循环．同时还得到，在Ｇ的最大对集中边数为μ（Ｇ）的一个下界，即μ（Ｇ）≥（ｎ－｜β（Ｇ）－１｜）／２．对于非欧拉图Ｇ，令ψ（Ｇ）＝β（Ｘ（Ｇ，Ｇ）），和用γ（Ｇ）表示这样边的最小数目，使得在将它们从Ｇ中收缩掉而得到的图上，有边属于奇数个完满对集．我们证明，γ（Ｇ）＝ψ（Ｇ）以及μ（Ｇ）≥（ｎ－ψ（Ｇ））／２．     

关于CockayneEJ的两个猜想

猜想１〔１〕当Ｋ（Ｇ）＝Ｃ２ｎ＋１时有Ｃ（Ｇ）≤ｄ（Ｇ）;猜想２〔１〕当Ｋ（Ｇ）是偶图时有Ｃ（Ｇ）≤ｄ（Ｇ）．以下通过反例说明猜想１不成立．然后证明猜想２成立．设Ｇ是无向、无环、无多重边的简单图,Ｇ＝（Ｖ,Ｅ）,其中Ｖ＝Ｖ（Ｇ）表示Ｇ的顶点集,Ｅｎ＝...     

关于不含长导出路的图的一个标记

一个不含具有ｔ个顶点的导出路的图被称为Ｐｔ自由的，一个连通图Ｇ的ｉ－中心是由Ｖ（Ｇ）中所有距其它任何顶点的距离不大于ｉ的顶点组成的集合，对于Ｖ（Ｇ）的两个子集Ｓ和Ｔ，如果对任何ｘ∈Ｔ都有ｙ∈Ｓ，使得ｘ距ｙ的距离不大于ｄ，则称Ｓｄ－支配Ｔ，本解决了由Ｏ．Ｆａｖａｒｏｎ和Ｊ．Ｌ．Ｆｏｕｑｕｅｔ提出的一个公开问题，即证明了如下结果：对任何Ｐｔ－自由图Ｇ，如果ｉ≥／ｔ／２／且ｐ≥１，则Ｃｉ（Ｇ）（ｐ＋１     

6长圈加1条弦的图设计

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

七点有向θ图的图设计

设Kv是一个v点的有向完全图,G是一个简单有向图,Kv的一个G-设计,记为(v,G,1)-GD,是指一个二元组(X,B),其中X为Kv的点集,B为Kv的一些子图(也称为区组)构成的集合,使得任一子图(区组)与G同构,且Kv的任意两个不同点组成的有向边恰在B的一个区组中出现。研究了七点有向图的图设计的存在性问题。     

一类六点八边图的图设计

设Kv是一个v个点的完全图,G为Kv的一个不含孤立点的简单子图.Kv的一个G-设计,常记为(v,G,1)-GD,是指一个二元组(X,B),其中X为Kv的顶点集,B是Kv的一些子图(亦称为区组)构成的集合,使得每一个区组与G同构,且Kv的任何一条边恰在B的一个区组中出现.文章讨论了一类六点八边图中尚未解决的3个图Gi(i=1,2,3)的图设计存在性问题,并证明了(v,G,1)-GD(i=1,2,3)存在的必要条件v=0,1(mod 16)且≥16也是充分的.从而给出了这类六点八边图图设计存在的完全解.     

大围长图中控制圈的一个局部条件

设Ｇ是围长大于或等于５的连通图．本文证明了；如果对Ｇ中每个顶点ｖ，距离ｖ为２和３的顶点导出的子图的独立数不大于最小度的两倍减３，那么Ｇ中有控制圈．     

关于（k—1）容错直径或k直径的最大图

本文确定了阶为ｎ，（ｋ－１）容错直径为ｄ或ｋ直径为ｄ的ｋ连通图Ｇ的边数的最大值，并给出了相应的最大图．     

准可分解4-星设计

设λKv表示v个顶点λ重的完全图.一个4-星设计是指有序对（X,B）,其中X=V（λKv）,B是一些同构于4-星的子图（称为区组）的集合,使得λKv中每一条边恰好出现在B的唯一区组中.如果B能划分为平行类（顶点集的划分）,则（X,B）为可分解4-星设计;若B能划分为准平行类（顶点集去一点的划分）,则（X,B）为准可分解4-星设计.在可分解4-星设计存在的充分必要条件基础上,证明了准可分解4-星设计存在的必要条件v≡1（mod 5）,λ≡0（mod 8）也是充分的.     

三角连通[4,2]-图的完全圈可扩性

如果G的任意s个点的导出子图中至少含有t条边,则称图G为[s,t]-图.本文证明了:若G是无孤立点的三角连通[4,2]-图,则G或者是完全圈可扩的或者同构于F.其中图F有与图■∨K2同构的导出子图.     

关于Faudree－Schelp定理的改进

一个图Ｃ＝（Ｖ，Ｅ）是［ｌ，ｍ］－泛连通的，如果在Ｇ的任意一对节点ｘ与ｙ之间有长为Ｋ—１的路Ｐｋ（ｘ，ｙ），Ｋ＝ｌ，ｌ＋ｌ，…，ｍ。Ｇ具有性质Ｐ（Ｋ），如果对Ｇ的任何一对距离为２的节点ｘ和ｙ，有ｄ（ｘ）＋ｄ（ｙ）≥Ｋ。作者探讨了一类产（Ｋ）图的路连通性，改进了Ｆａｕｄｒｅｅ－Ｓｃｈｅｌｐ定理，得到两个定理：定理１设Ｇ＝（Ｖ，Ｅ）是ｎ阶Ｐ（ｎ—１）图。如果Ｇ是［ｎ—１，ｎ］－泛连通的，则Ｇ是［８，ｎ］－泛连通图（ｎ≥８）．定理２设Ｇ是３－连通ｎ阶Ｐ（ｎ）图。如果Ｇ的独立数α（Ｇ）＜ｎ／２，则Ｇ是［５，ｎ］－泛连通图，ｎ≥５．     

阶数不小于6的强-[s，t]图的泛圈性

一个图G为强-[s,t]图,如果G中任意s个顶点的集合S的导出子图中至少含有t条独立边,本文证明了阶数≥6的强-[4,2]图是泛圈的。