图的禁用子图和H—连通性

证明了如下结果：设Ｇ是３—连通图，如果Ｇ满足如下之一：（ｉ）｛Ｋ１，３，Ａ，Ｄ）－ｆｒｅｅ．（ｉｉ）｛Ｋ１，３，Ａ，Ｐ５｝－ｆｒｅｅ．（ｉｉｉ）｛Ｋ１，３，Ｉ｝－ｆｒｅｅ．（ｉｉｉｉ）｛Ｋ１，３，Ｚ３，Ｂ｝－ｆｒｅｅ．则Ｇ是Ｈ－连通的．     

2和3连通图中的禁止子图与哈密顿性质

证明了如下结果：（１）若Ｇ是２－连通的（Ｋ１，３，Ｐ５，Ｂ）－自由图，或２－连通的（Ｋ１，３，Ｚ２，Ｐ５）－自由图，则Ｇ是哈密顿图，（２）若Ｇ是３－连通的（Ｋ１，３，Ｚ１）－自由图，或３－连通的（Ｋ１，３，Ｚ２，Ｐ５）自由图，或３－连通的（Ｋ１，３，Ｐ５，Ｂ）－自由图，则Ｇ是哈密顿连通的。     

两个完全图Kn和Kr＋2关于Kr—粘合的色等价类

设Ｇｎ是ｎ阶广义树,则Ｐ（Ｇｎ）＝λ（λ－１）＾ｒ１．．．（λ－ｍ）＾ｒｍ,其中１＋ｒ１＋．．．＋ｒｍ＝ｎ,且当ｎ〉１时,ｒｉ≥１（ｉ＝１,２,．．．ｍ）。设色等价类｛Ｇ,Ｋ｝＝｛｛ｒ１,ｋ２,ｒ２ｋ３,,ｒｍＫｍ＋１｝,｛（ｒ１－１）Ｋ,ｒ２Ｋ２,,ｒｍＫｍ｝｝。证明了,如果Ｐ（Ｇ）＝Ｐ（Ｇｎ）,则Ｇ是一棵广义树当且仅当｛Ｇ,Ｋ｝是一个完全类。在ｒｉ＝ｒｉ＋１＝２,ｒｊ＝１（ｊ≠ｉ,ｉ＋１）时     

Hamilton连通图的一个充分条件

设Ｇ是ｎ阶３－连通图，若对任意不相邻二点｛ｕ，ｖ｝Ｖ（Ｇ）有ｄ（ｕ）＋ｄ（ｖ）＋２｜Ｎ（ｕ）∪Ｎ（ｖ）｜≥２ｎ＋１，则Ｇ是Ｈａｍｉｔｏｎ连通的。     

涉及距离的哈密顿连通图

证明了下面的结论：设Ｇ是ｎ阶３－连通图，如果对任意满足ｄｉｓｔ（ｕ，υ）＝２的顶点｛ｕ，υ）（Ｇ），有ｍａｘ｛ｄ（ｕ），ｄ（υ）｝＋｜Ｎ（ｕ）∪Ｎ（υ）｜≥ｎ＋１，则Ｇ是哈密顿连通的．     

1坚韧图中过给定点子集的圈

设Ｇ是阶１－坚韧图，Ｘ是Ｇ的顶点子集合，定义（Ｘ）＝ｍａｘ｛│Ｓ││Ｓ是秀导子图Ｇ［Ｘ］中的顶点独立集｝，σｋ（Ｘ）－ｍｉｎ｛Σ＾ｋｉ＝１（１，２，…ｋ｝是独立集｝和ｃ（Ｘ）＝ｍａｘ｛│Ｖ（Ｃ）∩Ｘ││Ｃ是Ｇ中的圈｝。我们得到如下主要结果：设Ｇ是阶１－坚韧图，并且σ３（Ｘ）≥，则ｃ（Ｘ）≥ｍｉｎ｛│Ｘ│，│Ｘ│＋δ＾－（Ｘ）－α（Ｘ）＋１│，并且这下界是最好的，这时δ（Ｘ）是不小于     

2-连通正则图中最长ab-路

在 Ｈ．Ａ．Ｊｕｎｇ定理的基础上，讨论Ｔ ２－连通正则图中最长 ａｂ－路 Ｐａｂ的路长。设Ｇ是ｎ阶ｋ正则具有二分类（Ｖ１，Ｖ２）的偶图，对任意ａ，ｂ∈Ｖ（Ｇ）．ａ≠ｂ， 若有或 ａ． ｂ ∈ Ｖ２则称Ｇ有Ｈａｍｉｌｔｏｎ性质。一个非偶图若是Ｈａｍｉｌｔｏｎ连通的，则称为具有Ｈａｍｉｌｔｏｎ性质。限制｛ａ，ｂ｝不是Ｇ的割集，具有上述性质的Ｇ称为有弱Ｈａｍｉｌｔｏｎ性质。作者得到如下定理：令Ｇ是２－连通ｋ正则的图，且｜Ｇ｜≤３ｋ－２（ｋ≥９）．则Ｇ有弱Ｈａｍｉｌｔｏｎ性质。     

一个关于2─连通图周长的次条件

设Ｇ为ｎ阶２－连通图，顶点ｖ１，ｖ２，…，ｖｎ满足ｄ１≤ｄ２≤…≤ｄｎ，其中ｄｉ＝ｄ（ｖｉ），ｉ＝１，２，…，ｎ。给出ｃ（Ｇ）≥ｍｉｎ｛ｎ，ｍ｝的如下条件：     

一个Hamilton图的邻域交条件

设Ｇ是２－连通图．如果对其任一３－独立集｛ｘ１,ｘ２,ｘ３｝,有ｘｉ（１≤ｉ≤３）使得Ｎ（ｘｉ）与∪ｊ≠ｉＮ（ｘｊ）至少有α（Ｇ）个公共元素,则Ｈａｍｉｌｔｏｎ图．这里,α（Ｇ）是Ｇ的独立数．     

用基本集讨论k－连通图的Hamilton－连通性

设Ｇ是ｎ阶ｋ－连通图（ｋ≥３）．称Ｇ的独立集Ｓ为一个基本集，如果存在｛ｕ，ｖ｝Ｓ使得ｄｉｓｔ（ｕ，ｖ）＝２．本文证明了下述结论：如果对Ｇ的任－ｋ－基本集Ｓ，有ｍａｘ｛ｄ（ｕ）｜ｕＳ｝≥　则Ｇ或者是Ｈａｍｉｌｔｏｎ－连通的或者属于两类例外图之一。     

偶图的周长

设Ｇ（Ａ，Ａ２；Ｅ）为２连通偶图，（Ａ１，Ａ２）为顶点二分划，Ｄ（ｘ）＝｛ｙ｜ｙ∈Ｖ（Ｇ）＼｛ｘ｝，ｄ（ｘ，ｙ）＝２｝，ｄ＾＊ｄ（ｘ）表示Ｄ（ｘ）∪｛ｘ｝中所有的度排成的非减度序列（ｄ＾＊１，ｄ＾＊２，…，ｄ＾＊ｊ，…，ｄ＾＊｜Ｄ（ｘ）｜＋１）中当下标ｊ＝ｄ（ｘ）时的度而当｜Ｄ（ｘ）｜＋１＜ｄ（ｘ）时ｄ＾＊ｄ（ｘ）＝ｄ＾＊｜Ｄ（ｘ）｜＋１。δ０＝ｍｉｎ｛ｄ（ｘ）｜ｘ∈Ｖ（Ｇ）｝，δｉ＝ｍｉｎ｛ｄ＾     

图的升分解问题的两个新结果

Ａｌａｖｉ等人在１９８７年定义了图的一种新分解,即“升分解”（ＡｓｃｅｎｄｉｎｇＳｕｂｇｒａｐｈＤｅｃｏｍｐｏｓｉｔｉｏｎ）,并且猜想：任意有正数条边的图都可升分解．该文证明了下面两个新结果：（１）Ｈｉ是ｉ条边的Ｋｎ的子图,当ｎ＋１≤ｉ≤２ｎ－２ｎ／３［］２－２时,Ｇ＝Ｋｎ－Ｈｉ可升分解为Ｋ１,１,Ｋ１,２,…,Ｋ１,ｎ－５,Ｋ１,ｎ－４,Ｇｎ－３（ｎ≥６）,其中Ｋ１,ｎ－４Ｇｎ－３．（２）Ｈｉ是ｉ条边的Ｋｎ的子图,当ｉ≥２ｎ－２ｎ／３［］２时,Ｇ＝Ｋｎ－Ｈｉ不一定有定理１形式的升分解．     

一类无爪图的Hamilton圈

设ｖ是图Ｇ＝（Ｖ，Ｅ）的顶点，若存在顶点ｕ∈Ｖ－｛ｖ｝，使子图Ｇ［Ｎ（ｖ）∪｛ｕ｝中任意一对顶点的距离不超过３，则称ｖ是Ｇ的弱局部连通顶，点。设Ｇ是非平凡的连通无爪图，且它的任一顶点割均钫含一个弱局部连通顶点，则Ｇ包含Ｈａｍｉｌｔｏｎ圈。     

不含K3图的周长

设Ｇ为不含Ｋ３的２连通的非偶图的图。Ｄ（ｕ）｛ｖ｜ｖ∈Ｖ（Ｇ），ｄ（ｕ，ｖ）＝２｝，δ０＝ｍｉｎ｛ｍａｘ（ｄ（ｕ），ｄ（ｖ）｜ｕ，ｖ∈Ｖ（Ｇ）且ｄ（ｕ，ｖ）＝２｝，Ｄ（δ０）＝｛ｕ｜ｕ∈Ｖ（Ｇ）且ｄ（ｕ）≥δ０｝，δ≥δ０时还满；     

图的圈长分布和圈长分布唯一的图

阶为ｎ的图Ｇ的圈长分布是指序列（ｃ１，ｃ２，…，ｃｎ），其中ｃｉ是Ｇ中长为ｉ的圈数．若不存在，使Ｇ’与Ｇ有相同的圈长分布，则称图Ｇ是圈长分布唯一图．本文确定了Ｋｎ－Ａ（｜Ａ｜＝ｊ，ｎ≥｜Ａ｜＋３）的最小、最大的４圈和５圈数．证明了当ｎ≥９时，Ｋｎ－Ａ（｜Ａ｜＝４）以及当ｎ≥１４时，Ｋｎ－Ａ（｜Ａ｜＝５）都是圈长分布唯一图．     

极大平面图与外可平面图的同构不动边

图Ｇ的一条边ｅ称为Ｇ的同构不动边，如果当且仅当ｅ’＝ｅ．若ｅ＝ｕｖ是Ｇ的同构不动边，则对Ｇ—ｅ的任一自同构映射。都有π（｛ｕ，ｖ｝）＝｛ｕ，ｖ｝文中证明了，除Ｋ３Ｖ（Ｋ１＋Ｋ１；）外的极大平面图和除Ｐ２ＶＫ１，Ｐ３ＶＫ１外的２－连通外可平面图都含有同构不动边．     

关于图的分支因子

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

X-最长圈的下界估计

设Ｇ是连通图,Ｘ＝Ｖ（Ｇ）,Ｇ〔Ｘ〕是Ｇ的Ｘ生成子图,记σｋ（Ｘ）＝ｍｉｎ｛Σｉ＝１ ｋ ｄ（Ｖｉ）;｛ｖ１,ｖ２,…,ｖｋ｝是Ｇ〔Ｘ〕的顶点独立集｝,得到如下结果,对于ｎ阶的１－坚韧图（ｎ≥３）,Ｘ＝Ｖ（Ｇ）,且σ３（Ｘ）≥ｎ＋ｒ≥ｎ,３│Ｘ│－２ｎ≥８ｔ－６ｒ－１７,则存在一个圈Ｃ满足│Ｃ（Ｘ）│≥｛Ｃ（Ｘ）│≥｛│Ｘ│,│Ｎ（Ｉｔ）∩Ｖ（Ｃ）│｝,其中Ｉｔ是Ｘ中ｔ个顶点的独立集。     

简单连通图的k阶幂图的指数集(英文)

设Ｇ 是一个ｎ 阶简单连通图,ｋ≥２ 是一个整数．Ｇ 的ｋ 阶幂图记作Ｇｋ ,定义为：Ｖ（ Ｇｋ） ＝ Ｖ（ Ｇ） 且对任意ｕ ,ｖ∈Ｖ（ Ｇｋ） （ ｕ≠ｖ） ,（ ｕ ,ｖ） ∈Ｅ（ Ｇｋ） 当且仅当ｄＧ（ ｕ ,ｖ） ≤ｋ ,则对任意的ｋ≥２ ,Ｇｋ 本原．令Ｅ（ｋ,ｎ） ＝ ｛ γ（ Ｇｋ）｜ Ｇ 是ｎ阶简单连通图｝ ,可以得到Ｅ（ｋ ,ｎ） ＝ｄｋ ｋ＋ １ ≤ｄ ≤ｎ － １ ,　　若２ ≤ｋ≤ｎ － ２ ,｛２｝ ,　　　　　　　　　　　　若ｋ≥ｎ － １ ．     

关于Cayley图因子的一个注记

Ｃａｙ（Ｓ：Ｇ）表示生成集为Ｓ的群Ｇ上的Ｃａｙｌｅｙ图。本文证明了如下结果：定理ｌ若Ｈ＝Ｃａｙ（Ｓ１：＜Ｓ１＞），则Ｃａｙ（Ｓ：Ｇ）有Ｈ－因子。定理２设Ｓ＝Ｓ１∪Ｓ２∪…∪Ｓｋ，ｓｉ∩Ｓｊ＝φ（ｉ≠ｊ），Γｉ＝Ｃａｙ（Ｓｉ：＜Ｓｉ＞），则Ｃａｙ（Ｓ：Ｇ）是｛Γ１，Γ２，…，Γｋ｝──可分的。