图的联结数与分数k-消去图

设G是一个图,若对于图G的任一条边e,G-e都存在一个分数k-因子,则称G是一个分数κ-消去图.若k=2,则称分数κ-消去图为分数2-消去图.本文证明了当bind(G)≥2,并且6(G)≥3时,G是分数2-消去图.     

图的分数因子与孤立韧度

图G的孤立韧度定义为I(G)=min{｜S｜/i(G-S)∶SV(G),i(G-S)≥2},若G不是完全图.否则令I(G)=∞.本文给出了图的分数k因子与图的分数[a,b]因子的存在性与图的孤立韧度的关系.证明了,若δ(G)≥k且I(G)≥k,则G有分数k因子;若δ(G)≥I(G)≥a-1 a/b,则图G有分数[a,b]因子,其中a相似文献   

关于诱导子树与图的色数的一个注记

Gyrfs(1975)和Sumner(1981)分别独立地提出了以下猜想:对于任意的树T,存在一个函数f_T(x)使得每一个色数大于f_T(ω(G))的图均包含T作为诱导子图,其中ω(G)表示图G的团数.Gyrfs等(1980)证明了,若一个图G不含三角形和长为4的圈,则G含有任一个χ(G)个顶点的树作为诱导子图.另外,他们还证明了,若G不含三角形,且χ(G)≥m+n,则G一定包含一个特殊的树(m,n)-mop作为诱导子图.本文推广了Gyrfs等(1980)的这两个结果,证明了(1)若图G的任一个顶点至多含在k个三角形和l个长为4的圈中,且χ(G)≥t+2k+2k,则G包含任一个t个点的树作为诱导子图;(2)若图G中的每一个顶点至多包含在k个三角形中,且不能够诱导出T,则χ(G)m(k+1)+n,其中T为(m,n)-mop.     

Hamiltonian[k,k+1]-因子

本文考虑n/2-临界图中Hamiltonian[k,k+1]-因子的存在性。Hamiltonian[k,k+1]-因子是指包含Hamiltonian圈的[k,k+1]-因子;给定阶数为n的简单图G,若δ(G)≥n/2而δ(G\e)相似文献   

Mutlhews—Sumner定理的证明

本证明了：若G是2连通无爪图且δ（G)≥n-2/3，则G是Hanmilton图．     

关于图的结合数的一个猜想

本文对图论中的Woodall关于结合数的一个猜想作了研究,证明了:若图G的结合数,则图G包含三角形,从而较好地改进了文献[1]中的一个结果.     

一个定理的简单证明

本文对文献[1]的部分结论给出了一个很简单的证明。本文讨论的图是无向简单图。用d_G(v)或者d(v)表示图G中顶点v的次或度。用G[U]表示点集U的导出子图。其余符号见[2]。设G是一个图,|V(G)|=p,若k是给定的非负整数,若对图G中每一对不相邻的顶点u和v,都有d(u) d(v)≥p k,则称图G为Ore-k型图。     

一类新的泛圈图

本文所说的图都是简单无向图。未定义的术语和记号参见[2]。设 G=(V,E)的 n 阶图(n≥3),若 G 中含有 Hamilton 圈,则称 G 是 H-图。若G 中含有从3到 n 的所有长度的圈,则称 G 为泛圈图。如下两个定理是众所周知的。定理1 (Ore,1960)。若在 n 阶图 G 中,有uv(?)E(G)(?)d(u) d(v)≥n,则 G 是 H-图。     

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为弱泛圈图.     

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等人也得到完全相同的结果,但本证明更简捷.     

THE BINDING NUMBER OF A GRAPH AND ITS TRIANGLE

In this paper we prove the following conjecture of Woodall:if bind(G)≥3/2,then Gcontains a triangle.Moreover,we also prove that if bind(G)≥3/2,then each vertex is contained ina 4-cycle,each edge is contained in a 5-cycle when V(G)≥11,and there exists a 6-cycle in G.     

关于Win猜想的部分结果

<正> 本文假定G=(V,E)是2n个点的简单图,我们用C[U]表示点集U的导出子图,用d(x)表示G中点x的次,d_H(x)表示G的子图H中点x的次.其余符号见[3]. 给定非负整数k,若图G中每一对不相邻的顶点u和ν,都有d(u)+d(ν)≥2n+k,则称G为Ore k-型图.S.Win给出下述猜想: 若G是Ore k-型图,则G有k+2个1-因子.其中k≤2n-4.     

图的上可嵌入性的邻域条件

用NG（u）表示一个图G中任意点u的邻域集．本文主要证明了下述结果：设G是无环图,对G中任意相邻的点u和υ,即uυ∈E（G）,若如下两条件之一满足：（1）|NG(u)∩NG(υ)≥2;（2）G是2-点连通的图,且|NG(u)∩NG(υ)|≥1,则G是上可嵌入的．     

平面图的绑定数

图G的绑定数b(G)是指边集合的最少边数,当这个边集合从G中去掉后所 得图的控制数大于G的控制数． Fischermann等人在[3]中给出了两个猜想: (1)如果 G是一个连通的平面图且围长g(G)≥4,则b(G)≤5;(2)如果G是一个连通的平面图且 围长g(G)≥5,则b(G)≤4．设n3表示度为3的顶点个数,r4和r5分别表示长为4和 5的圈的个数．本文,我们证明了如果r4<(5n3)/2 10,则猜想1成立;如果r5<12,则猜 想2成立．     

超级限制边连通二部图的充分条件

设S是连通图G的一个边割.若G-S不包含孤立点,则称S是G的一个限制边割.图G的最小限制边割的边数称为G的限制边连通度,记为λ'(G).如果图G的限制边连通度等于其最小边度,则称图G是最优限制边连通的,简称λ'-最优的.进一步,如果图G的每个最小限制边割恰好分离出图G的一条边,则称图G是超级限制边连通的,简称超级-λ'的.设G是一个最小度δ(G)≥2的n≥4阶二部图,ξ(G)是G的最小边度.本文证明了(a)若ξ(G)≥(n/2-2)(1+1/δ(G)-1),则G是λ'-最优的;(b)若ξ(G)>(n/2-2)(1+1/δ(G)-1),则G是超级-λ'的,除非图G是K2,n-2,n≥6或是Cartesian积图Kn/4,n/4×K2,其中n≥8且n整除4.最后,论文举例说明该结果是最好可能的.     

独立集的度和与图的哈密尔顿性

关于哈密尔顿连通图的一个基本结果是Ore给出的：设G是n阶图,若对于任意两个不相邻顶点u和v,有d(u) d(v)≥n 1,则G是哈密尔顿连通的．设G是一个图,对于任意u (?)V(G),令N(U)=∪_(u∈∪)N(u),d(U)=|N(U)|,称d(U)是U的度．本文利用独立集的度和得到如下结果：设s和t是正整数,G是(2s 2t 1)-连通n阶图．若对于任两个强不交独立集S,T,|S|=s,|T|=t,有d(S) d(T)≥n 1．则G是哈密尔顿连通的．同时也得到图的哈密尔顿性的其它相关结果．两个独立集S和T称为强不交的,如果S∪T也是独立集．     

[a,b]-对等图的范-型条件

既是[a,b]-覆盖又是[a,b]-消去的图称为[a,b]-对等图.设1≤aan+1a+b,则G为[a,b]-对等图.给出了一个图是[a,b]-对等图的关于范-型条件及邻域并的若干充分条件,并指出定理中的条件在一定意义上是最好可能的.     

图的联结数与分数κ-消去图

设G是一个图,若对于图G的任一条边e,G-e都存在一个分数k-因子,则称G是一个分数k-消去图.若k=2,则称分数k-消去图为分数2-消去图.本文证明了当bind（G）≥2,并且δ（G）≥3时,G是分数2-消去图.     

汉米尔顿图泛圈性的奥尔型条件

本文所说的图是简单图,未定义的术语见[1,2].n 阶图 G,n≥3,若有长为 n 的圈,则说 G 是汉米尔顿图;若对每个 k,3≤k≤n,G 含有长为 k 的圈,则说 G 是泛圈图.定理1.在 n 阶图 G 中,若对任何点对 x,y∈V(G),xy(?)E(G),都有 d(x)+d(y)≥n,则 G 是汉米尔顿图.     

有约束条件的图的分数k-因子

设G是一个简单的无向图，若G不是完全图，G的孤立韧度定义为I(G)=min{｜s｜／i(G-S)：S∈V(G)，i(G-S)≥2)；否则令I(G)=∞．对与图的孤立韧度I(G)密切相关的新参数，I’(G)，若G不是完全图，定义I’(G)=min{｜s｜/i(G-S)-1:S∈V(G)，i(G-S)≥2}；否则I’(G)=∞本文研究了新参数I‘(G)与图的分数κ-因子的关系，给出了具有某些约束条件的图的分数κ-因子存在的一些充分条件．