Hamilton非二部图的弱泛圈性

图G称为弱泛圈图是指G包含了每个长为t(g(V)≤l≤c(G))的圈,其中g(G),c(v)分别是G的围长与周长.1997年Brandt提出以下猜想:边数大于[n2/4]-n 5的n阶非二部图为弱泛圈图.1999年Bollobas和Thomason证明了边数不小于[n2/4]-n 59的n阶非二部图为弱泛圈图.作者证明了如下结论:设G是n阶Hamilton非二部图,若G的边数不小于[n2/4]-n 12,则G为弱泛圈图.     

关于唯一r——泛圈图

唯一r—泛圈图G是一个简单图,对n=r,r+1,…,p,(r≥3,p=|V(G)|),G恰含一个圈C_n,但G不含圈C_t,3≤t≤r-1。R.C.Entringer于1973年提出:确定是唯一泛圈图的简单图(唯一泛圈图指的是唯一3—泛圈图)。文[3]确定了具有p+m(m≤4)条边的图及外平面图中的唯一泛圈图。本文得到:当r≥4时, 1.外平面图G是唯一r—泛圈图当且仅当G≌C_P; 2.具有p+2条边的图不是唯一r—泛圈图; 3.具有p+3条边的图没有唯一r—泛圈图,5≤r≤p;但恰有6个唯一4—泛圈图,且这样的图仅有6个.     

正则图的邻强边染色和全染色

如果~$k$-\-正则图~$G$~不含~5-\-圈的分支, 则猜测~$\chi''_{\mathrm{as}}(G) = \chi_{\mathrm t}(G)$. 证明这个猜想对很多图类都成立, 例如: 第1类型图、 $2$-\-正则图、$3$-\-正则图、$(|V(G)|-2)$-\-正则图、二部图、完全等多部图、$k$-\-方体以及一些特殊的联图类等.     

关于图与圈之并图的圈唯一性

Farrell[1]引进图 G 的圈多项式 c(G;■).文[6]猜测:轮形图 W_8是圈唯一的.本文中我们证明上述猜测为真且讨论了某些图与圈之并图的圈唯一性.     

修正冒泡排序网络的边偶泛圈性

对于一个二部图G,如果在G中存在任意长为偶数l(4≤l≤|V(G)|)的圈,则称这个二部图G是偶泛圈的:如果对G中任意一边e,在G中存在任意长为偶数l(4≤l≤|V(G)|)且包含e的圈,则称这个二部图G是边偶泛圈的.修正冒泡排序网络是互连网络中的一个重要的Cayley图模型.在此,证明了对任意的自然数n,当n≥3时,修正冒泡排序网络Y_n是偶泛圈的,同时也是边偶泛圈的.     

关于几乎唯一泛圈图

设G是阶为n的简单Hamilton图．若存在m(3(?)m＜n)使对每个l∈{3,4,…,n} -{m},G恰有一个长为l的圈且不含长为m的圈,则称G是几乎唯一泛圈图,用(?)k表示具有n k条边和恰有1/2(k 1)(k 2)个圈的简单H图的集合,用(?)_k~*表示具有n k条边恰有2~k k个圈的简单外可平面H图的集合,本文确定了(?)_k和(?)_k~*中所有几乎唯一泛圈图,并证明这些图都是简单MCD图,本文还构造了50个含有同胚于K_4的子图的几乎唯一泛圈图,并提出了若干问题和猜想。     

几乎正则多部竞赛图的点泛圈性

令T是多部竞赛图,i(T)=x,()|d+(x)-d-(y)|(这里允许x=y)如果i(T)=0,则T被称为是正则的;如果i(T)≤1,则T被称为是几乎正则的.Volkmann猜测几乎正则c-部竞赛图(c≥4)是泛圈的.本文证明当c≥5时,除了有限多个几乎正则多部竞赛图外,所有几乎正则c-部竞赛图都是点泛圈的.同时我们给出一个反例说明当c=4时,上述猜想不成立.     

一类几乎唯一泛圈图

设G是阶为n的简单Hamilton图．若存在m(3(?)m相似文献   

几乎正则多部竞赛图的点泛圈性

令T是多部竞赛图;i（T）=|d+（x）-d-（y）|（这里允许x=y）,如果i（T）=0,则T被称为是正则的;如果i（T）≤1,则T被称为是几乎正则的.Volkmann猜测几乎正则c-部竞赛图（c≥4）是泛圈的.本文证明当c≥5时,除了有限多个几乎正则多部竞赛图外,所有几乎正则c-部竞赛图都是点泛圈的.同时我们给出一个反例说明当c=4时,上述猜想不成立.     

边不交圈的图的符号差(英文)

一个有限简单图的符号差是指其邻接矩阵的符号差,即邻接矩阵的正惯性指数和负惯性指数的差.马海成等猜测一个图的符号差小于等于长度为4k+5圈的个数,大于等于长度为4k+3圈的个数的负值,本文证明了该猜测对边不交圈的图是成立的.     

双圈覆盖问题

Seyntour[1]与Szekeres[5]猜想，每一个无割边的图G具有一个圈集合 使G中的每个边存在于 的两个圈中。本证明此猜想成立当且仅当它对没有非平凡的三个边割的图成立。     

关于3正则图的三匹配交猜想(Ⅱ)

Fan和Raspaud 1994年提出如下猜想：任一无桥3正则图必有三个交为空集的完美匹配．本文证明了如下结果：若G是一个圈4-边连通的无桥3正则图，且存在G的一个完美匹配M1使得G—M1恰为4个奇圈的不交并，则存在图G的两个完美匹配M2和M3使得M1∩M2∩M3=Φ。     

无爪图泛圈性的邻域并条件

证明了,若G是一个p-阶3-连通无爪图,p≠10,11,15,并对G中任意两个不相邻的点u和v,满足|N(u)∪N(v)|≥(p-1)/2,则G是泛圈图.     

一类泛圈图

本证明了如果G是2连通无爪图,G不是圈,n=|V(G)1≥9,G的每个导出子圈A都满足φ（a1,a2),且G中不含同构于Z^ 2的导出子图,则G是泛圈图。     

一类线图的泛圈性

本文的主要结果是:设G是n≥3阶简单图,ε≥2,且不含3度的边,若GC_4,C_5及C_4∪K_1且对任意无公共顶点的两边e_1和e_2,有d(e_1) d(e_2)≥2n-3,则G的线圈L(G)是泛圈图。     

K1,4-自由的模κ泛圈图

设G是2-连通的K1，4自由图．本文证明了当δ(G)≥κ 1时，G是模κ泛圈图．这一结果肯定了猜想2，继而也肯定了Thomassen猜想在2-连通图中的正确性．     

Bondy的泛圈图定理的改进

记G=(V,E)是简单图,1971年Bondy得到O re条件下的泛圈图的著名结果:若2连通n阶图G的不相邻的任两点x、y均有d(x) d(y)≥n,则G是泛圈图或G=Kn/2,n/2.这里进一步研究条件d(x) d(y)≥n-1,得到:若2连通n阶图G的不相邻的任两点x、y均有d(x) d(y)≥n-1,则G是泛圈图或G∈{K(Cn 1)/2∨G(n-1)/2,Kn/2,n/2}.本文作者得知最近国际著名权威专家Ho lton等人也得到完全相同的结果,但本证明更简捷.     

邻域并与泛圈图

本文中 ,我们用邻域并对泛圈图进行深入的研究 ,主要取得了“2连通 n( n≥ 3 )阶图 G,满足下列条件之一 ,则 G是泛圈图 : :δ≤ ( n-7) /3 ,N C≥ ( 2 n-3 ) /3 ; :( n-6) /3≤ δ≤ ( n+2 ) /3 ,N C≥ 2 n/3 ; :δ≥ ( n+3 ) /3 ,N C≥ ( 2 n-3 ) /3 .当 3≤ n≤ 14时 ,N C≥ 2 n/3”     

关于3正则图的三匹配交猜想(Ⅰ)

Fan和Raspaud 1994年提出如下猜想任一无桥3正则图必有三个交为空集的完美匹配. 本文研究一类特殊的无桥3正则图G存在图G的一个完美匹配M1使得G-M1恰含有两个奇圈和若干偶圈. 在偶圈数≤2的情形以及在偶圈数≤4且G是圈4-边连通的情形,本文证明了一定存在图G的两个完美匹配M2和M3使得M1∩M2∩M3=φ.     

Jackson正则图定理的一个注记

§1.引言关于简单图上简单圈的研究,最近 Jackson 在[2]中证明了一个相当好的定理:任何一个δ正则的2-连通图 G,如果其顶点个数 n 满足n≤3δ,则 G 中存在一个 Hamilton圈。Jackson 在文章中还提到他相信在δ≥4时把 n 的限制放宽到 n≤3δ+1 是可能的。要证实他的这种看法是否成立,只须对 n=3δ+1 时来证明就行了。