HAMILTON图的特征矩阵

讨论了Hamilton图G和它的邻接矩阵A之间的关系，得到如下结果定理1：图G是H－图当且仅当A＝B＋Q，这里B≥0且B≠0，Q＝PCP，C是由互换单矩阵中的第1行和第n行所得到的初等阵，P是置换阵，P是P的转置矩阵，定理：图G是H－图当且仅当A的谱半径ρ（A）是A的单根，且存在正特征向量ξ，使得Aξ＝ρ（A）ξ＞η，这里η是适当调整ξ的分量而得到的向量，满足：当ξ的第i个分量调为η的第j个分量时，A的（i,j)元aij=1.     

关于随机相交图中Hamilton圈的门限函数的注记

随机相交图G（n，m，p）的定义如下：记V为-n,顶点集．M-m个元素的集合．对每个顶点v∈V，赋予一随机子集Fv包含M，其中从M中独立以概率p选取每个元素构成Fv，顶点u和v之间有边相连当且仅当Eu∩Fv≠Ф．当m=n^a，a≠1时．C．Efthymiou和P．G．Spirakis得到了G（n，m，p）中Hamilton圈的门限函数．对于a=1情形，本文利用二阶矩方法（Chebyshev不等式）得到了类似结果．     

一类新的泛偶圈图

一个2n阶偶图G,如果有长为2R(2≤R≤n)的圈,则称其为泛偶圈。本文证明了如下结果:设G=(X,Y,E)是一个2n阶连通偶图。如果G中任意一对距离为3的顶点的次数之和不小于n+1,则G是泛偶圈的,除非是长为6的圈。     

一类图中的最长圈

引言 Dirac曾经证明,如果简单图G的最小次δ满足δ≥|G|/2,则G是Hamilton图。记为G∈H。Ore改进到,若f=min{d(u)+d(v)|uv(?)E(G)}≥|G|,则G∈H,Jung[1]又改进到,若,则G∈H。这里S是V(G)的真子集,G/S是从G中除去S所得的图,K(G/S)是图G/S的连通分支的数目,最小是在所有K(G/S)≥2的S上取的。     

一类亚几乎唯一泛圈图

设G是阶为n的简单Hamilton图,若存在不同的p,q(3≤p相似文献   

一类无爪图的Hamilton圈

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

4类图完美匹配数目的嵌套递推求法

用划分,求和再递推的方法分别给出了图3-n3LC4, 3-nBC4, 3-nL4和1-nXC4的完美匹配数目的计算公式,所给出的方法可以计算出许多特殊图的所有完美匹配的数目. 并利用所得到的计算公式计算出了一类图的Hamilton圈的数目.     

关于一类Ore图的泛圈性

从所周知，ＪＡＢｏｎｄｙ的Ｍｅｔａｌ猜测对Ｏｒｅ图是成立的。本文从一个新的角度，对Ｇ中次数较小的节点所导出的子图的结构进行了分析，得出了一类新的泛圈图。     

若干图联图的边联结数

本文研究了路、圈、完全图相互间经过联运算以后所得图的边联结数,得到了Lm(?)Ln,Cm(?)Cn,Lm(?)Cn,Lm(?)Kn和Cm(?)Kn的边联结数的计算公式,这里Lx,Cx,Kx分别表示有x个点的路、圈、完全图。     

矩形网格中Hamilton圈个数的计算

讨论了n×m阶矩形网格(其中n和m中至少有一个为偶数)中 Hamilton圈个数F(n,m),获得下列结果:F(n,3)=2~(n/2-1),对任何偶数n;F(n,4)=2[F(n-1,4)+F(n-2,4)-F(n-3,4)+F(n-4,4),对n≥6;F(n,5)=11F(n-2,5)+2F(n-6,5),对≥8的偶数n;其中F(2,4)=1,F(3,4)=2,F(4,4)=6,F(5,4)=14,F(2,5)=l,F(4,5)=14,F(6,5)=154。 本文也指出n×m阶矩形网格的两点间的平均距离等于(n+m)/3,且对于k维空间推广了这个结果。     

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

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

几类图的联结数

本文给出了若干完全图的联(nK_r+mK_s),圈、路和完全二部图分别与完全图的补图的字典式积(C_m(K_n)、L_m(K_n)和K_(a,b))以及完全r—部图(K_(n1,n2,…nr))等几类图的联结数。     

关于图的可达划分数

本文给出了E.J.Cockayne和S.T.Hedetniemi的下列猜想的一个新证明:当图G的团图为2-分图时,G的最小团的阶数不大于G的可达划分数;讨论了图的可达划分数与连通度的关系。     

哈密尔顿图的一类新的局部化充分条件

设L为图G的一个导出子图 ,若有 x ,y∈V(L) ,只要dL(x ,y) =2就有max{dG(x) ,dG(y) }≥ |G| / 2 ,则称L有局部Fan性质 .该文证明了以下结果 .G是一个 2_连通的 {K1.3 ,B1} -free图 .对任意一个整数s≥ 0 ,若G的任一个导出子图L∈ {Bi,0≤i≤s;Zs+2 }均有局部Fan性质 ,则G是Hamiltonian图 ,除非s=2且G H9.由此得到每个 2_连通的 {K1.3 ,Bi,0≤i≤s;Zs+2 }_free图除s =2且该图同构于H9外 ,均为Hamiltonian图 .     

关于图全着色的几个结果

引入了一种研究图全着色问题的新方法，即从考虑图中的圈出发研究全着色问题．运用该方法确定了一些图的全色数，并给出了图全色数的一个上界．     

广义轮型完全多部图的生成树数

证明了如下结论:设KWk,n是由轮图集W={Wn1,Wn2,…,Wnk}生成的n阶广义轮型完全k-部图,其中n={n1,n2,…,nk},n=|n|=n1+n2+…+nk,1≤k≤n.那么KWk,n的生成树数目为t(KWk,n)=n2k-2∏ki=1αni-1i+βni-1i-2n-ni+1,其中αi=(di+d2i-4)/2,βi=(di-d2i-4)/2,di=n-ni+3.     

分数Hamilton圈与分数树形图

定义有向图的分数有向Hamilton圈和分数支撑树形图，讨论分数Hamilton圈、分数旅行售货员问题和分数支撑树形图基于线性规划的等价定义及多项式时间算法。