一个关于图是[a,b;n]-均匀的度条件

设t,a,b和n为整数且1≤a＜b,t≥3以及n≥1.如果G的导出子图不含有K1,t,则该图G称为K1,t-无爪图.如果对于图G中含有n条边的任意匹配M,都在G中有[a,b]-因子F包含M以及在G中有另一个[a,b]-因子F'不包含M,则图G称为[a,b;n]-均匀图.给出了K1,t-无星图G是[a,b;n]-均匀图的度条件.进一步,指出本文中的结果在某种意义上说是最佳的.     

3—连通局部连通无爪图是泛连通图

本文证明了若G是连通、局部连通的无爪图,则G是泛连通图的充要条件为G是3-连通图.这意味着H.J.Broersma和H.J.Veldman猜想成立.     

[a,b]-因子存在性的范-型条件

设G是一个图,a,b是整数且满足0≤a≤b.如果存在G的一个支撑子图F,使对任意的x∈V(G)有a≤d_F(x)≤b,则称F是G的一个[a,b]-因子.本文给出图中具有特定性质的[a,b]-因子的范-型条件.进一步指出这个结果是最好的.     

图的[a,b]-因子存在性的两个结果

设G是一个图,a,b是整数且满足0≤a≤b.如果存在G的一个支撑子图F,使对任意的x∈V(G)有a≤dF(x)≤b,则称F是G的—个[a,b]-因子.本文给出图中具有特定性质的[a,b]-因子的两个充分条件.     

[a,b]-因子包含给定圈的充分条件

设G是一个图且a,b是非负整数,a≤b.图G的一个[a,b]-因子是图G的一个支撑子图H且满足对所有的x∈V(G),a≤dH(x)≤b都成立.给出了图中[a,b]-因子包含给定圈的一个充分条件.     

(a,b,C_k)临界图的判定

设G是一个图且a,b是非负整数,a≤b.如果消去G中的任意一个k-圈,剩下的图有[a,b]-因子,则称图G是(a,b,C_k)-临界图.给出了图是(a,b,C_k)-临界图的充分条件.     

独立数与最小度和[a，b]-因子

设G是一个图,a,b是整数且0≤a≤b,G的一个支撑子图F称为一个[a,b]-因子,若对任意的v∈V(G)有a≤dF(v)≤b.在本文中,我们给出了图存在[a,b]-因子涉及到独立数和最小度的一个充分条件,推广了前人的结果.     

图的分数因子与孤立韧度

图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相似文献   

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

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

图的联结数与[a,b]-因子存在性

设G是一个n阶图,a,b,m1,m2是非负整数且满足1≤a＜b和b≥m1.H1和H2是图G的两个边不交的子图且满足|E(H1)|=m1和|E(H2)|=m2.证明下列结论:若图G的联结数bind(G)＞(a+b-1)(n-1)/bn-(a+b)-2(m1+m2)+2且n≥(b-1)(a+b-1)(a+b-2)+2b(m1+m2)/b(b-1),则图G有一个[a,b]-因子F满足E(H1)(∈)E(F)和E(H2)∩ E(F)=φ.进一步指出这个结果是最好的.     

P3-支配图哈密尔顿性的两个充分条件

在文献[3]中介绍了一个新的图类-P3-支配图.这个图类包含所有的拟无爪图,因此也包含所有的无爪图.在本文中,我们证明了每一个点数至少是3的三角形连通的P3-支配图是哈密尔顿的,但有一个例外图K1,1,3.同时,我们也证明了k-连通的(k≥2)的P3-支配图是哈密尔顿的,如果an(G)≤k,但有两个例外图K1,1,3 and K2,3.     

Induced subgraphs with large degrees at end-vertices for hamiltonicity of claw-free graphs

A graph is called claw-free if it contains no induced subgraph isomorphic to K1,3. Matthews and Sumner proved that a 2-connected claw-free graph G is Hamiltonian if every vertex of it has degree at least (|V(G)|-2)/3. At the workshop C&C (Novy Smokovec, 1993), Broersma conjectured the degree condition of this result can be restricted only to end-vertices of induced copies of N (the graph obtained from a triangle by adding three disjoint pendant edges). Fujisawa and Yamashita showed that the degree condition of Matthews and Sumner can be restricted only to end-vertices of induced copies of Z₁ (the graph obtained from a triangle by adding one pendant edge). Our main result in this paper is a characterization of all graphs H such that a 2-connected claw-free graph G is Hamiltonian if each end-vertex of every induced copy of H in G has degree at least |V(G)|/3+1. This gives an affirmative solution of the conjecture of Broersma up to an additive constant.     

图有含(或不含)特殊边的[a,b]-因子的邻域条件

设G是一个n阶图.设1≤a＜b是整数.设H1和H2是G的任意两个边不交子图,它们分别具有m1和m5条边,以及δ(G)表示最小度.证明了若δ(G)≥a+m 2,n≥2(d+b-m2)(a+b-m1-1)/(b-m1),a≤b-(m1+m2),并且|NG(x)UNG(y)|≥an/(d+b-m1)+2m2对任意两个不相邻的顶点x和y成立,那么G有[a,b]-因子F使得F含有H1的边并不含H3的边.     

Discussion on Fractional (a,b, k)-critical Covered Graphs

Acta Mathematicae Applicatae Sinica, English Series - A graph G is called a fractional [a, b]-covered graph if for each e ∈ E(G), G contains a fractional [a, b]-factor covering e. A graph G...     

(a,b,n)-临界图的几个充分条件

设G是一个图 .设g和f是两个定义在V(G)上的整值函数使得对V(G)所有顶点x有g(x) ≤f(x) .图G被称为 (g ,f,n) 临界图 ,如果删去G的任意n个顶点后的子图都含有G的 (g ,f) 因子 .本文给出了图是 (a ,b ,n) 临界图几个充分条件 ,即度和邻域条件 .进一步指出这些条件是最佳的 .     

图有[a,b]因子的邻域条件

不含有图K1，R的图称为K1,r-free图，设G是一个具有顶点集V（G）的图，设n(≥3),a和b是整数，使得b≥a≥1，若b是奇数，设b≥n-1。我们证明了每个连通的K1,r-free图G在b|V(G)|为偶数，它的最小度至少是a n-1,|V(G）≥ （2(a b)-1)(a b-1)/b，以及|NG(x）∪NG（y)|≥a|V(G)|a b对V的任意两个不邻接的点x和y都成立时，G有一个[a,b]因子。     

最大度不小于5的外平面图的邻强边染色

图G(V,E)的一k-正常边染色叫做k-邻强边染色当且仅当对任意uv∈E(G)有,f[u]≠f[v],其中f[u]={f(uw)|uw∈E(G)},f(uw)表示边uw的染色.并且x'as(G)=min{k|存在k-图G的邻强边染色}叫做图G的图的邻强边色数.本文证明了对最大度不小于5的外平面图有△≤x'as(G)≤△ 1,且x'as(G)=△ 1当且仅当存在相邻的最大度点.