对Hamilton图性质的一个改进

n阶图G称为Hamilton图是指G包含一个长为n的圈,Bollbás曾证明了在Hamilton图H中,若边数e(H)≥n24-n+59,则H必含长为(n-1)的圈或具有特殊结构的长为(n-2)的圈.我们认为条件e(H)≥n24-n+59可以进一步减弱,本文证明了在e(H)≥n24-n+15的条件下,结论同样成立.

一类有向图为Hamilton图的判定

利用邻接矩阵研究有向图的Hamilton问题.讨论了研究有向图的Hamilton图的充要条件.设矩阵A为具有n个顶点的严格有向图D的邻接矩阵,则D为有向Hamilton图的充要条件为A的行列式的展…ajnj1非零.开式中至少有一项(-1)τ(j1j2…jn)+τ(j2j3…jnj1)

Hamilton图的一个充要条件

解决了一类Hamilton图的判别即衍生图是Hamilton图 ,并给出了这类图求Hamilton圈的算法 ,进而得到一个Hamilton图的充要条件 .

Hamilton图的一个充要条件

通过对图的关联矩阵与回路矩阵的正交性讨论,得出用基底关联矩阵A=(A11 A12)计算基本回路矩阵Bf的公式Bf=(U AT11(A-112)T);根据计算出的基本回路矩阵Bf的特征,得到一个判定Hamilton图的充要条件——图的基本回路矩阵中必有一行有且仅有n个非零元素(n为图的顶点数).

判别Hamilton图的一个方法

本文研究寻找Hamilton的圈的一个方法,证明了如下定理:设G是单图,V（G）={V1,V2,…,Vn},则G是Hamilton图的充分必要条件是Xki取1或0时,方程组（*）有解,其中sum from i=1 to n sum from j=1 to n xkixk+1jViVj=1而x（n+1）j=x1j sum from i=1 to n xki2=1 sum from i=1 to n xik2=1 而ViVi=1 当Vi和Vj邻接时, 0 当Vi和Vj不邻接时。

一些新的Hamilton图的必要条件

寻求Hamilton图的适当的特征刻画是图论的一个重大未解决问题,根据图的结构特征,设计了图的顶点的分层方法,研究了Hamilton图中层与层间对外顶点数和对外边数应该满足的关系,分析了Hamilton图中每层顶点数与每层对外顶点数的关系,探讨了图与其Hamilton演化图的Hamilton性关系,最后得到一些新的Hamilton图的必要条件。所获得的新的Hamilton图的必要条件实用性强,使用方便,能判断一些原必要条件不能判断的非Hamilton图。

有向图为Hamilton图的一个充分条件

在文献[2]中,B ang-Jensen等人猜想,如果对n阶强连通有向图D中每一对不相邻的,且具有公共内邻或公共外邻的顶点对x,y,都有它们的度和不小于2n-1,则D是H am ilton图.本文证明若对上述x,y,如果它们的度和不小于2n-1与52n-92中的最大者,则D是H am ilton图.

HAMILTON图的特征矩阵

讨论了Hamilton图G和它的邻接矩阵A之间的关系,得到如下结果定理1 图G是H—图当且仅当A=B+Q,这里B≥0且B≠0,Q=P CP,C是由互换单位矩阵中的第1行和第n行所得到的初等阵,P是置换阵,P是P的转置矩阵。定理2 图G是H—图当且仅当A的谱半径ρ(A)是A的单根,且存在正特征向量ξ,使得Aξ=ρ(A)ξ>η,这里η是由适当调整ξ的分量而得到的向量,满足:当ξ的第i个分量调为η的第j个分量时,A的(i,j)元a_(ij)=1。

一类3-正则3-连通平面Hamilton图(英文)

设Γk是由带如下结构的3-正则3-连通平面图G所组成的图类:G中含一个圈C,使得G-E(C)产生k个不相交的树,并且每个树具有至少三条边.本文证明了Γ1中所有的图都是Hamilton图.

一个新的充分条件和Hamilton图

在前人工作的基础上,创立进一步的新条件,得到结果:记δ为图G的最小度,若2连通n阶图G的距离为2的任意两点x和y均有max{d(x),d(y)}≥n/2或|N(x)∪N(y)|≥n-δ,则G是Hamilton图.

一类HAMILTON图中圈的数目

Yap H P和Teo S K提出问题:下述等式是否成立?m(K)=(1/2)(k+1)×(k+2),M(k)=2~k+k。此外,对于任意介于m(k)与M(k)之间的整数i,是否存在G∈H(n,k)使得f(G,k)=i?本文解决了上述问题。

一类Hamilton图

若P[u ,v]是 2连通无爪图G的最长路 ,设dp(xβ,xα) =︱P[xβ,xα]︱ -1 (xβ<xα) ,d P(xα,xβ) =|P[xα,xβ]|-1 (xα≤xβ) ,其中xα∈N(u) ,xβ∈N(v) ·dP=min{d(xβ,xα)︱xα∈N(u) ,xβ∈N(v) } ·d P =min{d(xα,xβ)︱xα∈N(u) ,xβ∈N(v) } ·设P[u,v]是具有最小dP 的G的最长路·采用反证法 ,将图G分为若干情况 ,利用P[u ,v]的定义 ,证明了 :若G是 2连通无爪图 ,且G的每个导出子图A ,A1都满足 φ(a1,a2 ) 。

一类Hamilton图

一个 n 阶自补图 G 满足(1)当 n≡1(mod 4)对,对每一u∈V(G)皆有 d_G(u)=(n-1)/2;(2)当 n≡0(mod 4)时,d_G(u_i)=n/2,1≤i≤n/2,d_G(v_j)=n/2-1,1≤j≤n/2,这里 V(G)={u_1,…,u_(n/2),v_1,…,v_(n/2)},则称 G 为拟正则自补图,简称 q.r.s.c 图。本文证明了2n 阶(n-1)度正则连通图以及任意 n 阶(n≥5)q.r.s.c 图都是 H-图。

分数Hamilton图的充分必要条件

分数Hamilton图是比Hamilton图更广泛的图类.作者借用线性规划的知识给出了判定分数Hamilton图的新的充分必要条件,并利用新的充分必要条件对特殊图类的分数Hamilton图进行了研究.

Hamilton图的一个注记

本文的主要结果是：设G是D－圈图，若存在某个t≤δ，使得对任何t＋1个点的独立集，X＝｛x0，x1，…，xz），有，则G是Hamilton图。

一类图簇的Hamilton图的研究

通过研究图的伴随多项式的因式分解,得到了若干构造性的Hamilton图簇.

pq^2阶Cayley图是Hamilton图

根据pq^2阶群构造,运用超可解群理论证明了pq^2阶连通Cayley图是Hamilton图.

Hamilton图的判定

对任意简单连通图Ｇ，其作为Ｈａｍｉｌｔｏｎ图的充分必要条件是图Ｇ中不含病态顶点和病态圈，或者其简图是Ｈａｍｉｌｔｏｎ图。并且。

判别Hamilton图的一个充要条件

本文利用图的邻接矩阵给出了有限无向连通图成为Hamilton图的一个充分必要条件。

Hamilton图的矩阵变换判别法

利用图的邻接矩阵与一种特殊矩阵置换相似的关系判别图中Hamilton圈(路)的存在情况。首先对于不完全图的无向图和有向图进行分析,给出不完全图和完全图存在Hamilton圈(路)的充分必要条件,然后得出了竞赛图寻找Hamilton圈(路)的简单方法。