部分平方图的独立集和1-几乎Hamilton性

借助于部分平方图独立集讨论了图的 1 几乎Hamilton性 ,得到G是 1 几乎Hamilton图的一个充分条件 .

关于几乎正则2-连通图的Hamilton性的注记

研究几乎正则图的Hamilton性,得到了定理1 设G是2连通的(k,k+1)图,并且k≥V(G)3+13,如果G是偶数阶的图,则G是Hamilton图.定理2 设G是(k,k+2)图,并且k≥n3+103,如果存在G的一个非空独立集B1,使得B1≥n3-133,而且对于G的所有独立集B,都有B≤n2-1,则G是Hamilton图.

几乎Hamilton连通图和部分平方图(英文)

G为图 ,G 是G的部分平方图 .运用 (k + 2 )连通图 (k≥ 2 )上的插点技术 ,借助LTW序列对G 中独立集的邻域交加权 。

几乎完全图是由第二Immanantal多项式刻画的

令M=(m_(ij))表示n阶方阵.矩阵M=(m_(ij))的第二immanant定义为d_(2)(M)=∑_(σ∈S)nχ(σ)∏_(s=1)^(n)m_(sσ(s))其中χ表示S n关于划分(2,1,…,1)的不可约特征标.令G是一个含有n个顶点的图,L(G)表示图G的拉普拉斯矩阵.多项式d_(2)(x I-L(G))表示图G的第二imamnantal多项式,其中I表示n阶单位矩阵.本文证明了几乎完全图是由第二imamnantal多项式确定的.

几类梯状图的完美匹配与Hamilton圈

循环梯状图CLn是由圈Cn和路p2的笛卡尔积CLn=Cn×p2(n≥3),Möbius梯状图MLn是通过梯子图Ln添加边a1bn和b1an得到。删掉CLn和MLn的一个Hamilton圈(删边不删点)后剩下的子图是它们的一个完美匹配。反之,删掉CLn和MLn的一个完美匹配后剩下的子图只要是连通的,那一定是原图的Hamilton圈。因此本文通过删除完美匹配的方法给出了Ln,CLn和MLn的所有Hamilton圈,进而通过Hamilton圈研究了完美匹配之间的关系。

关于几乎唯一泛圈图

设G是阶为n的简单Hamilton图．若存在m（3≤m〈n）使对每个l∈{3，4，…，n}-{m}，G恰有一个长为l的圈且不含长为m的圈，则称G是几乎唯一泛圈图．用Гκ表示具看n＋κ条边和恰有互1（κ＋1）（κ＋2）个圈的简单H图的集合．用Г^＊κ表示具有n＋κ条边恰有2^κ＋κ个圈的简单外可平面H图的集合．本文确定了^-Гκ和Г^＊κ中所有几乎唯一泛圈图，并证明这些图都是简单MCD图．本文还构造了50个含有同胚于K4的子图的几乎唯一泛圈图，并提出了若干问题和猜想．

[s,t]-图及其Hamilton性

一个图G叫[s ,t] -图,如果G中任意s个点的导出子图中至少含有t条边.本文讨论了某些[s,t] -图的Hamilton性质.

2r-正则图连通圈网络的Hamilton分解

互连网络是超级计算机的重要组成部分。互连网络通常模型化为一个图,图的顶点代表处理机,图的边代表通信链路。2010年师海忠提出互连网络的正则图连通圈网络模型,设计出了多种互连网络,也提出了一系列猜想。文中证明了2r-正则图连通圈网络可分解为边不交的一个Hamilton圈和一个完美对集的并,从而证明了当原图为2r-正则连通图时,这一系列猜想成立。

边色临界图的1-因子和几乎1-因子的存在性

根据Vizing邻接引理和关于临界图的独立数的一个结论,利用图的1-因子和几乎1-因子存在的充要条件,采用结构图论的方法证明了:1)若G是2n阶Δ-临界图,且Δ≥n,δ≥n-2,则G存在1-因子;2)若G是2n+1阶Δ-临界图,且Δ≥n+1,δ≥n-2,则G存在几乎1-因子.

2-连通[5,3]-图中的Hamilton圈

如果G中任意s个点的导出子图中至少含有t条边,则称图G为[s,t]-图.证明了若G是顶点数不小于8且δ(G)≥3的2-连通[5,3]-图,则G含有Hamilton圈.

一个求简单图中所有Hamilton回路的算法

从Hamilton回路的定义和图的邻接矩阵的定义入手,建立了图中的初级通路的关联关系.利用长度为k的初级通路及其关联关系逐步求长度为k+1的初级通路及其关联关系的方法,求得图的所有Hamilton回路.通过理论分析,说明该算法比已有的求图的所有的Hamilton回路的算法降低了算法的复杂度,为求解Hamilton回路问题提供了新思路.

有限交换群上Bi-Cayley图的Hamilton性

设G是一个有限群,S是G的一个子集(可以含G的单位元).Bi-Cayley图BC(G,S)是一个二部图:其顶点集为G×{0,1},而边集为{{(g,0),(sg,1)}:g∈G,s∈S}.本文证明了有限交换群上连通的Bi-Cayley图BC(G,S)是Hamilton的,如果S-1=S且S含二阶元或单位元.

Petersen图的Hamilton性和边色数(英文)

对简单图G(V ,E) ,定义图G的关联图I(G)为V(I(G) ) ={ (ve)｜v∈V(G) 且e∈E(G) 和v与e关联 } ,E(I(G) ) ={ (ue ,vf)｜u=v或e=f或uv =e或uv=f} .本文证明了Petersen图可被分解为边不交的Hamilton 圈和一个 1

对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的条件下,结论同样成立.

一类二部图的几乎完美匹配数(英文)

图 的一个 匹配称 为几 乎完美 匹配，若 它覆 盖了一 个顶点 以外 的所有 顶点． 本文 给出具 正 Ｓｕｒｐ ｌｕ ｓ二部图有 Ｖ（ Ｇ）＋ １个几乎 完美匹配的两个

连通、几乎局部连通拟无爪图是完全圈可扩的

G是一个图 ,B(G)表示G中所有局部不连通的点构成的集合 .如果B(G)是独立集 ,并且对任意v∈B(G) , u∈V(G) ,使G[N(v)∪ {u}]连通 ,则称G是几乎局部连通的 .如果G中所有爪心构成的集合D(G)是独立集 ,并且对任意v∈D(G) ,G[N(v) ]是强 2 -控制的 ,则称G是拟无爪图 .本文证明 :连通、几乎局部连通的拟无爪图是完全圈可扩的 .

图的Hamilton问题的着色否定方法

就具有Hamilton路或Hamilton圈的图的着色否定方法展开了讨论,并给出了相关的结论.

2-连通T_3-受限图的Hamilton性

部分K1,3的一条边所得到的图记为T3,其中的3度顶点称为T3的中心.如果图G的任意一个同构于T3的导出子图,除中心以外的4个顶点之间的边数≥3,则称G为T3-受限图.本文主要证明:如果GF′,2-连通T3-受限图G含有Hamilton图.

严格有向图Hamilton路的研究

利用图论的基本方法及其思想,结合相关定义、定理提出了两个严格有向图含有向Hamilton路的两个充分条件,即D为具有n(≥2)个顶点的严格强连通有向图:1)如果对任意具有共同的内邻点或者具有共同的外邻点的非邻接顶点对{x,y},都有d(x)+d(y)≥2n+1,且min{d+(x)+d-(y),d-(x)+d+(y)}=n-2,则有向图D含有向Hamilton路;2)如果对任意具有共同内邻点或者具有共同的外邻点的非邻接顶点对{x,y},都有d(x)+d(y)≥(5/2)n-5,则有向图D含有向Hamilton路.

Cayley图的Hamilton性

设Ｇ是一个有限群，Ｇ＝＜Ｍ＞．Ｇ上的一个Ｃａｙｌｅｙ图Ｘ（Ｇ，Ｍ）定义如下：Ｖ（Ｘ）为Ｇ，Ｅ（Ｘ）是所有无序对（ａ，ｂ）组成的集合，其中ａ，ｂ∈Ｇ，ａ－１ｂ∈Ｍ∪Ｍ－１，Ｍ－１＝｛ｘ－１｜ｘ∈Ｍ｝．如果Ｍ中含有素数阶正规元ａ，那么以下结果被证明：（ｉ）若Ｘ（Ｇ／＜ａ＞，Ｍ）是Ｈａｍｉｌｔｏｎ图，则Ｘ（Ｇ，Ｍ）是Ｈａｍｉｌｔｏｎ图．（ｉｉ）若Ｘ（Ｇ／＜ａ＞，Ｍ）是边－Ｈａｍｉｌｔｏｎ图且ａ为生成元，则Ｘ（Ｇ，Ｍ）是这－Ｈａｍｉｌｔｏｎ图．（ｉｉｉ）若Ｘ（Ｇ／＜ａ＞，Ｍ）是边－Ｍａｍｉｌｔｏｎ图且存在元ｘ∈Ｍ，使得ｘａ＝ａｘ，则Ｘ（Ｇ，Ｍ）是边－Ｈａｍｉｌｔｏｎ图．