k-连通无爪图中存在哈密尔顿圈的一个隐度条件

文中给出了强基本独立集的概念,并证明了如下定理:设G是一个具有n个顶点的k-连通无爪图,其中k≥2.如果对任意一个具有k个顶点的强基本独立集S,都有max{d2(x)|x∈S}≥n 2,则G是哈密尔顿图.此定理在无爪图的条件下推广了已有的几个有关图中哈密尔顿圈存在性的定理.     

图的坚韧度与哈密尔顿圈

本文研究了图的线坚韧度的性质及线坚韧度与点坚韧度之间的关系,并利用坚韧度给出图是 哈密尔顿国的一个充分条件。     

简单图中哈密尔顿圈的个数

给出了计算简单图中哈密尔顿圈个数的几个公式,并对简单图中哈密尔顿圈个数的上下界进行了讨论。     

哈密尔顿连通图和邻域并条件（Ⅰ）

记G=(V,E)是简单图,δ表示图G的最小度,NC=min{|N(x)∪N(y)|：x,y∈V（G）mxt∈E（G）|,NC2=min{|N（x）∪N(y)|：x,y∈V(G),d(x,y)=2},1989年Faudree等证明了：若3连通n阶图G,NC≥(2n 1)／3,则G是哈密尔顿连通图。据此进一步研究NC2≥(2n 1)／3,而且研究到2连通图,得到下面结果：若2连通n阶图G,NC2≥(2n 1)／3,则G是哈密尔顿连通图或G=ψ。     

关于强哈密尔顿连通有向图的一个反例

Thomassen猜测,每个3强连通、顶点数为n、最小度至少为n+1的有向图是强哈密尔顿连通的.文章指出了这个猜测是错误的,并证明了,存在无限多个3强连通的、最小度至少为n+1的非强哈密尔顿连通有向图.     

哈密尔顿连通的度和与邻域交条件

Let S^23 denote an independent set with mini dist (u,v)|u, v∈S} = 2 and |S|=3. Our main result is the following theorem: Let G be a 3-connected graph of order n such that d(u) d(v) d(w)≥n 1 |N(u)∩N(v)∩N(w)|for any independent set S^23={u,v,w}, then G is Hamilton-connected.     

圆有向图的（1,2）步竞争图中存在哈密尔顿圈的条件

针对圆有向图的(1,2)步竞争图的结构,提出了竞争图中是否存在哈密尔顿圈;通过特殊到一般的方法得到如下结论:对于阶数n(n≥5)的强连通圆有向图的(1,2)步竞争图中存在哈密尔顿圈,而其余情形的圆有向图的(1,2)步竞争图中则不存在哈密尔顿圈。     

蕴含强哈密尔顿连通性的几个条件

利用收缩技术,推广了有向图理论中哈密尔顿性问题的几个结论,给出了有向图是强哈密尔顿连通的最小半度、度和、最少边数等条件．     

2-连通三圈图的零化度

本文所考虑的图均为无向简单图．图G的特征多项式的根称为图G的特征值,也构成图G的谱．图G的谱中零根的个数称为该图的零化度,记为η（G）．设Gn表示所有顶点数为n的图的集合,[0,n]=0,1,2,…,n,非空子集N∈[0,n]．若对A↓k∈N,都E←G∈Gn,使得η（G）=k,则N称为Gn的零化策本文主要研究2-连通三圈图的零化度．     

哈密尔顿图与泛圈图的几个性质的探讨

让NC＝min｛U（x)∪N(y)||x,y∈V(G),xy不属于E（G|｝,R.J.Faudree等曾得到NC≥n-δ,则G是哈密尔顿图。本文进一步研究NC≥n-δ-1的哈密顿性,推广了文前人的结果。     

分数k-消去图的度条件

设G是一个图,若对于图G的任一边e,G-e都存在一个分数k-因子,则称G是一个分数k-消去图.证明了当顶点数、最小度以及max{dG(u),dG(v)}(其中u,v是图中任意两个不相邻顶点)满足一定条件时,G是分数k-消去图,该结论在一定意义上是最好的.     

最大度是5的可平面图的边染色

对于最大度是Δ的可平面图G,如果χ′(G)=Δ,称G为第一类图;如果χ′(G)=Δ+1,称G为第二类图.χ′(G)表示G的边染色数.1965年,Vizing举例说明Δ=5的可平面图中既有第一类图,也有第二类图.作者运用Discharge方法证明最大度是5且不包含有弦的4-圈和有弦的5-圈,或不包含有弦的4-圈和有弦的6-圈的可平面图是第一类图.     

扭n立方体中的边不交Hamilton圈

网络图的Hamilton性是图论、计算机网络理论中的重要研究议题，超立方体及其变体由于其良好的网络参数、拓扑结构吸引了众多学者的关注和研究，并将之广泛地应用于许多实际领域中．结合Lee距离Gray码理论证明了扭n方体中存在[n／2]个边不交Hamilton圈，并且给出这些边不交Hamilton圈的生成方法．     

最大度等于5的图的强边色数

最大度等于5的图的强边色数至多为38.     

最大度是6的平面图是第一类图的一个充分条件

用x'(G)表示G的边染色数.对于最大度是△的可平面图G,如果X'(G)=△,称G为第一类图;如果x'(G)=△+1,称G为第二类图.运用Dischrge方法证明:最大度是6且不含7圈的可平面图G是第一类图.     

包含Vr（G）中所有顶点的圈

设Ｇ是一个ｎ阶２－连通图，ｒ是实数，并且，令Ｖｒ（Ｇ）＝｛ｖ∈Ｖ（Ｇ）｜ｄ（ｖ）≥ｒ｝．我们用Ｇ［Ｖｒ］表示由Ｖｒ（Ｇ）诱导的Ｇ的子图，ａ（Ｇ［Ｖｒ］）表示Ｇ［Ｖｒ］中的最大独立点数，σｋ（Ｇ）＝ｍｉｎ是Ｇ中的独立集｝．我们证明了如下结果，如果，则图Ｇ存在一个圈包含Ｖｒ（Ｇ）中的所有顶点．这个结果推广了Ｖｅｌｄｍａｎ的一个最新结果．并且解决了由朱永津教授提出的问题．     

Hamilton—图的一个充分条件

设G为n阶2-连通图,α为G的独立数.如果对于G中任意3个顶点的独立集{v_1,v_2,v_3}都有d(v_1)+d(v_2)+d(v_3)≥max{n+2,3α-2},则G是Hamilton-图。     

图的最长路与最长圈

路和圈是图论最基本的概念之一,Euler图问题和Hamilton问题都可归结为路和圈的研究．此外,路和圈在特定图中存在条件是我们最为关注的问题,而最长路和最长圈的研究更是引人入胜．本文就此问题作了较全面的回顾,并提出一些问题,供研究、探讨。     

二分图含圈与对集的一个构造性证明

给出了一个二分图G =(V1 ,V2 ;E)有一个支撑子图包含一个指定长度的圈和一个对集的度条件 .并且证明了若 |V1 |=|V2 |=n =2k ,则G有一个 2 因子恰有一个 8 圈和k 2个 4 圈或恰有k个 4 圈 .