图的分数κ-因子

给定图Ｇ＝（Ｖ,Ｅ）．设ａ和ｂ是两个非负整数．是一个函数．如果对所有的均成立,称 ｆ为 Ｇ的一个分数［ａ,ｂ］－ 因子． ａ＝ ｂ＝ κ时,称ｆ为 Ｇ的一个分数 ｋ＝因子．本文给出了一个图有分数 ｋ－因子的充分必要条件．     

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

Acta Mathematicae Applicatae Sinica, English Series - A fractional [a, b]-factor of a graph G is a function h from E(G) to [0, 1] satisfying $$a \le d_G^h(v) \le b$$ for every vertex v of G, where...     

图的分数k-因子

给定图G=(V,E).设a和b是两个非负整数.fE→［0,1］是一个函数.如果     

Toughness and [a,b]-factors with inclusion/exclusion properties

In this paper, we investigate the existence of [a,b]-factors with inclusion/exclusion properties under the toughness condition. We prove that if an incomplete graph G satisfies t(G) (a-1) + ab and a,b are two integers with b > a > 1, then for any two given edges e1 and e2, there exist an [a,b]-factor including e1,e2; and an [a,b]-factor including e1 and excluding e2; as well as an [a,b]-factor excluding e1,e2 unless e1 and e2 have a common end in the case of a = 2. For complete graphs, we obtain a similar r...     

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

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

2-连通无爪图的连通因子

若图G不含有同构于K1,3的导出子图,则称G为一个无爪图.令a和b是两个整数满足2≤a≤b.本文证明了若G是一个含有[a,b]因子的2连通无爪图,则G有一个连通的[a,b 1]因子.     

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

分数(g,f)-因子覆盖图

一个图称为分烽（g,f)- 因子覆盖图，如果G中的任何一条边e都包含在一个分数（g,f)- 因子中，并且满足h(e)=1，其中h是分数（g,f)- 因子的导出函数。本文给出了一个图是分数（g,f)- 因子覆盖图的充要条件。     

图有[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]因子。     

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

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

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

设G是一个图,a,b是整数且满足0≤a≤b.如果存在G的一个支撑子图F,使对任意的x∈V(G)有a≤d_F(x)≤b,则称F是G的一个[a,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相似文献   

一个关于图是分数(k,n)-临界的邻域并条件

设G是一个图,以及k是满足1≤k的整数.一个图G在删除任意n个顶点后的子图均含有分数k-因子,则称G是一个分数(k,n)-临界图.给出了图是一个分数(k,n)-临界图的一个邻域并条件,并且该条件是最佳的.     

关于分数(g,f)-因子消去图

一个图称为分数（g,f）－因子消去图，如果去掉图G中的任何一条边e图G仍有一个分数（g,f）－因子。本文分别给出了一个力是分数1－因子消去图和分数2－因子消去图的几个充分条件，并给出一个图有一个分数（g,f）－因子不含给定对集中任何一条边的充要条件。     

关于分数k-因子临界图与分数k-可扩图的若干结果

一个简单图G, 如果对于V(G)的任意k元子集S, 子图G-S都包含分数完美匹配, 那么称G为分数k-因子临界图. 如果图G的每个k-匹配M都包含在一个分数完美匹配中, 那么称图G为分数k-可扩图. 给出一个图是分数k-因子临界图和分数k-可扩图的充分条件, 并给出一个图是分数k-因子临界图的充分必要条件.     

Almost-regular factorization of graphs

For integers a and b, 0 ? a ? a ? b, an [a, b]-graph G satisties a ? deg(x, G) ? b for every vertex x of G, and an [a, b]-factor is a spanning subgraph F such that a ? deg(x, F) ? b for every vertex x of F. An [a, b]-factor is almost-regular if b = a + 1. A graph is [a, b]-factorable if its edges can be decomposed into [a, b]-factors. When both K and t are positive integers and s is a nonnegative integer, we prove that every [(12K + 2)t + 2ks, (12k + 4)t + 2ks]-graph is [2k,2k + 1]-factorable. As its corollary, we prove that every [r.r + 1]-graph with r ? 12k² + 2k is [2k + 1]-factorable, which is a partial extension of the two results, one by Thomassen and the other by Era.     

关于图中存在不含给定k-因子的[a,b]-因子的度条件

设$1\leq a<b, 0\leq k$是整数. 设$G$是一个含有$k$-因子$Q$且阶为$|G|$的图. 设\delta(G)$表示$G$的最小度, 且$\delta(G)\geq a+k$. 如果$Q$连通, 设$\varepsilon=k$, 否则设$\varepsilon=k+1$.证明:当$b\geq a+\varepsilon-1$时, 如果对$G$的任意两个不相邻的点$x$和$y$都有max$\{d_G(x),d_G(y)\}\geq {\rm max}\{{{a|G|} \over {a+b}},{{(|G|+(a-1)(2a+b+\varepsilon-2))} \over {b+1}}\}+k$, 那么$G$有一个$[a, b]$-因子$F$ 使得 $E(F)\cap E(Q)=\emptyset$. 这个度条件是最佳的, 条件$b\geqa+\varepsilon-1$不能去掉. 进一步,得到图存在含给定$k$-因子的$[a, b]$-因子的度条件.     

关于图的孤立韧度与分数因子存在性的若干结果

本文讨论了图的孤立韧度I(G)以及与之相关的参数I^1(G)与图的分数因子存在性的关系，给出了I(G)及I^1(G)与图的分数点(边)消去性、分数L-可扩性及分数[1，b]-因子存在性之间关系的一系列结果．     

图 P2×Cn的均匀邻强边色数

对图G(V,E),一正常边染色f若满足(1)对(V)uv∈E(G),f[u]≠f[v],其中f[u]={f(uv)|uv∈E};(2)对任意i≠j,有||E|-|Ej||≤1,其中Ei={e| e∈E(G)且f(e)=i}.则称f为G(V,E)的一k-均匀邻强边染色,简称k-EASC,并且称Xcas(G)=min{k|存在G(V,E)的一k-EASC为G(V,E)的均匀邻强边色数.本文得到了图P2×Cn的均匀邻强边色数.     

关于分数可消去图的若干结果

令G=(V(G),E(G))是一个图,并令9和f是两个定义在V(G)上的整数值函数且对所有的x∈V(G)有g(x)≤f(z)成立．若对G的每一条边e都存在G的一个分数(g,f)-因子G_h使得h(e)=0,其中h是G_h的示性函数,则称G是一个分数(g,f)-消去图,若在G中删去E′■E(G),|E′|=k后,所得图有分数完美匹配,则称G是分数k-边-可消去的。本文给出了图是1-可消去,2-可消去和k-边-可消去的与韧度和孤立韧度相关的充分条件。证明了这些结果在一定意义上是最好可能的．