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

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

关于Faudree定理的一个注记

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

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

设Ｇ为ｎ阶２－连通图，顶点ｖ１，ｖ２，…，ｖｎ满足ｄ≤ｄ２≤…≤ｄｎ，其中ｄｉ＝ｄ９ｖｉ），ｉ＝１，２，…，ｎ。给出ｃ（Ｇ）≥ｍｉｎ「ｎ，ｍ」的如下条件：ｊ〈ｋ，ｖｊｖｋ∈Ｅ，Ｊ＋Ｋ〈ｍ，ｄＪ≤Ｊ，Ｄｋ＋１≤ｋｄ（ｖ），ｄ（ｕ）≤Ｊ（其中Ｊ＝ｄ（ｖｊ），Ｋ＝ｄ９ｖｋ））｝→ｄｉｓｔ（ｖ，ｕ）≠２。     

X-最长圈的下界估计

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

简单无向连通图的k阶幂图的指数集

设Ｇ为简单无向图，以Ｖ＝Ｖ（Ｇ）为顶点集，以Ｅ＝｛（ｕ，ｖ）｜ｄ（ｕ，ｖ）≤ｋ｝为边集的图称为Ｇ的ｋ阶幂图。ｎ阶简单无向连通图的ｋ（ｋ≥２）阶幂图的指数集。     

关于图中给定端点的Hamilton—路及D—路

设Ｇ是有限无向简单图。｛ａ,ｂ｝等于包含于Ｖ（Ｇ）,Ｎ［ａ］＝Ｎ（ａ）∪｛ａ｝,令Ｊ（ａ,ｂ）＝｛ｕ│ｕ∈Ｎ（ａ）∩Ｎ（ｂ）且Ｎ（ｕ）等于包含于Ｎ［ａ］∪Ｎ［ｂ］｝。Ｇ＾＊称为Ｇ的部分平方图：Ｖ（Ｇ＾＊）＝Ｖ（Ｇ）,Ｅ（Ｇ＾＊）＝Ｅ（Ｇ）∪｛ａｂ│ａｂ不属于Ｅ（Ｇ）,Ｊ（ａ,ｂ）≠Φ｝。设Ｇ是（ｋ＋１）－连通图（ｋ≥２）,｛ｕ１,ｕ２｝等于包含于Ｖ（Ｇ）。本文主要结论：（ａ）设Ｇｗ是Ｇ中添加新顶点     

不含K3图的周长

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

领域并与点泛圈偶图

设Ｇ是连通偶图，（Ｘ１，Ｘ２）是其顶点的二分类，│Ｘ１│＝│Ｘ２│＝ｎ，δ（Ｇ）≥ｔ≥３。证明了若任意ｕ，ｖ∈Ｘｉ→│Ｎ（ｕ）∪Ｎ（ｖ）│≥ｎ－〔ｔ－１／２〕，ｉ＝１，２，则Ｇ是点泛圈图。     

图中含有k－因子的一个充分性条件

设ｋ是一不小于３的整数，Ｇ是连通图，具顶点数ｎ≥７ｋ－７，ｋｎ是偶数，且Ｇ的最小度δ（Ｇ）≥ｋ。本文证明了：若对Ｇ中任意一对不相邻的顶点ｕ、ｖ均有２ｎ－１≤ｄ（ｕ）＋ｄ（ｖ）十２｜（ｕ）ＵＮ（Ｖ）Ｄ，则Ｇ有ｋ一因子。     

关于图的泛连通性的几个结果

如果对ａ≤ｉ≤ｂ，图Ｇ的任一对顶点ｕ、ｖ都存在长为ｉ－１的路Ｐｉ（ｕ，ｖ），则称Ｇ是［ａｂ］－泛连通的．文中证明了关于图的泛连通性的下述结果：设Ｇ为ｎ阶连通图，且对Ｇ中任一对距离为２的顶点ｕ，ｖ，有ｄ（ｕ）＋ｄ（ｖ）≥ｎ，则图Ｇ是［５ｎ］－泛连通的当且仅当Ｇ是Ｈ连通的．此结果推广了Ｆａｕｄｒｅｅ和Ｓｃｈｅｌｐ的一个结论．     

局部化Fan条件的一个推广

对图Ｇ的任一个导出子图Ｌ,若对↓Ａｘ,ｙ∈Ｖ（Ｌ）,ｄＬ（ｘ,ｙ）＝２＝ｍａｘ｛ｄＧ（ｘ）,ｄＧ（ｙ）│≥│Ｇ│／２,则称Ｌ有局部Ｆａｎ性质,证明了下述结果：设Ｇ是一个２－连通图,若其每个导出子图Ｌ＝Ｋ１．３或Ｚ２在Ｇ中均有局部Ｆａｎ性质,则Ｇ是Ｈａｍｉｌｔｏｎｉａｎ图。     

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

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

一类OF图及其泛连通性

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

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

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

一类图的最长圈

设Ｇ是２－连通图。对Ｇ中任一对不相邻的顶点ｕ,ｖ,│Ｎ（ｕ）ＵＮ（ｖ）│≥ｓ当ｓ≥５时,对于事任意两个不主的点集Ｅ,Ｆ,│Ｅ│≥ｓ,│Ｆ│≥ｓ／２,Ｇ中有３条点不交的Ｅ－Ｆ路,由Ｇ的最长圈的长ｃ（Ｇ）≥ｍｉｎ｛│Ｖ（Ｇ）│,３ｓ／２｝。     

Hamilton连通图的一个充分条件

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

图的路连通问题

如果图Ｇ的每对不同顶点ｕ和ｖ之间都有哈密顿路相连，则称Ｇ是哈密顿连通的；而如果对于所有满足条件以ｄ（ｕ，ｖ）≤ｑ≤ｎ－１的整数ｑ，ｕ和ｖ之间有长为ｑ路相连，则和Ｇ是泛连通的，其中以ｄ（ｕ，ｖ）是ｕ和ｖ间的距离，而ｎ是Ｇ的顶点数。本文证明了下述两个结果：（１）２ｋ＋１个顶点的ｋ正则简单图是哈密顿连通的，（２）ｋ连通国中任何两顶点之间存在ｋ－１条长度不同的路；进而如果Ｇ的顶点数小于２ｋ，则Ｇ是泛连通的。     

（k＋1）——连通无爪图的Hamilton——连通性

一个图若不含与Ｋ１．３同构的导出子图,则称它为无爪图,本文利用Ｔ－插点方法,得到（ｋ＋１）－连通无爪图是Ｈａｍｉｌｔｏｎ－连通的两个充分条件,（１）设Ｇ是（ｋ＋１）－连通无爪图（ｋ≥２）,若对每个Ｘ∈Ｉｋ＋１（Ｇ）有ｓ２（Ｘ）〉１,则是Ｇ是Ｈａｍｉｌｔｏｎ－连通图,（２）设Ｇ是（ｋ＋１）－连通无爪图（ｋ≥２）,若对每个Ｘ∈Ｉｋ＋１（Ｇ）,有∑ｘ∈ｘｄ（ｘ）≥ｎ（ｘ）－ｋ＋１,则Ｇ是Ｈａｍｉｌｔｏｎ     

关于二分图的2-因子

证明：若Ｇ＝（Ｖｉ;Ｖ２;Ｅ）是一个二分简单图,│Ｖ１│＝│Ｖ２│＝ｎ≥２ｋ＋１且δ（Ｇ）≥〔ｎ／２〕＋１,那么Ｇ含一个２－因子,它恰有ｋ个分支。     

导出匹配可扩图的度和条件

称一个简单图Ｇ是导出匹配可扩的,缩写为ＩＭ－可扩的,如果Ｇ的每一个导出匹配都包含在一个完善匹配中,研究导出匹配可扩图的度和条件,主要结果如下：（１）若图Ｇ有２ｎ个顶点,且对于Ｇ中每一对不相邻的顶点ｕ和ｖ,ｄ（ｕ）＋ｄ（ｖ）≥２「４ｎ／３」－１,则Ｇ是出匹配可扩的;（２）若Ｇ是一有个有２ｎ个顶点的无爪图,且对于Ｇ中每一对不相邻的顶点ｕ和ｖ,ｄ（ｕ）＋ｄ（ｖ）≥２ｎ＋３,则Ｇ是导出匹配可扩的。同时,说