令G是一个有限图,H是G的一个子图.若V(H)=V(G),则称H为G的生成子图.图G的一个λ重F-因子,记为Sλ(F,G),是G的一个生成子图且可分拆为若干与F同构的子图(称为F-区组)的并,使得V(G)中的每一个顶点恰出现在λ个F-区组中.一个图G的λ重F-因...令G是一个有限图,H是G的一个子图.若V(H)=V(G),则称H为G的生成子图.图G的一个λ重F-因子,记为Sλ(F,G),是G的一个生成子图且可分拆为若干与F同构的子图(称为F-区组)的并,使得V(G)中的每一个顶点恰出现在λ个F-区组中.一个图G的λ重F-因子大集,记为LSλ(F G),是G中所有与F同构的子图的一个分拆{B_i}_i,使得每个B_i均构成一个Sλ(F,G).当λ=1时,λ可省略不写.本文中,我们证明了当v≡4 mod 24时,存在LS(K1,3,Kv,v,v).展开更多
A graph is said to be K1,3-free if it contains no K1,3 as an induced subgraph. It is shown in this paper that every 2-connected K1,3-free graph contains a connected [2,3]-factor. We also obtain that every connected K1...A graph is said to be K1,3-free if it contains no K1,3 as an induced subgraph. It is shown in this paper that every 2-connected K1,3-free graph contains a connected [2,3]-factor. We also obtain that every connected K1,3-free graph has a spanning tree with maximum degree at most 3.展开更多
Let h:E(G)→[0,1]be a function.If a≤∑e∋xh(e)≤b holds for each x∈V(G),then we call G[Fh]a fractional[a,b]-factor of G with indicator function h,where Fh={e:e∈E(G),h(e)>0}.A graph G is called a fractional[a,b]-c...Let h:E(G)→[0,1]be a function.If a≤∑e∋xh(e)≤b holds for each x∈V(G),then we call G[Fh]a fractional[a,b]-factor of G with indicator function h,where Fh={e:e∈E(G),h(e)>0}.A graph G is called a fractional[a,b]-covered graph if for every edge e of G,there is a fractional[a,b]-factor G[Fh]with h(e)=1.Zhou,Xu and Sun[S.Zhou,Y.Xu,Z.Sun,Degree conditions for fractional(a,b,k)-critical covered graphs,Information Processing Letters 152(2019)105838]defined the concept of a fractional(a,b,k)-critical covered graph,i.e.,for every vertex subset Q with|Q|=k of G,G−Q is a fractional[a,b]-covered graph.In this article,we study the problem of a fractional(2,b,k)-critical covered graph,and verify that a graph G withδ(G)≥3+k is a fractional(2,b,k)-critical covered graph if its toughness t(G)≥1+1b+k2b,where b and k are two nonnegative integers with b≥2+k2.展开更多
Let a,b,k,r be nonnegative integers with 1 ≤ a ≤b and r ≥ 2. Let G be a graph of order n with n 〉 （a＋b）（r（a＋b）-2）＋ak/a. In this paper, we first show a characterization for all fractional （a, b, k）-criti...Let a,b,k,r be nonnegative integers with 1 ≤ a ≤b and r ≥ 2. Let G be a graph of order n with n 〉 （a＋b）（r（a＋b）-2）＋ak/a. In this paper, we first show a characterization for all fractional （a, b, k）-critical graphs. Then using the result, we prove that G is all fractional （a, b, k）-critical if δ（G） ≥ （r-1）b2/a ＋k and ｜NG（xl） ∪NG（x2） ∪... ∪NG（xr）｜ ≥ bn＋ak/a＋b for any independent subset {xl, x2, .., xr} in G. Furthermore, it is shown that the lower bound on the condition ｜NG（xl） ∪NG（x2） ∪... ∪NG（xr）｜ ≥ bn=ak/ a＋b is best possible in some sense, and it is an extension of Lu＇s previous result.展开更多
A fractional[a,b]-factor of a graph G is a function h from E(G)to[0,1]satisfying a≤d^(h)_(G)(v)≤b for every vertex v of G,where d^(h)_(G)(v)=∑e∈E(v)h(e)and E(v)={e=uv:u∈V(G)}.A graph G is called fractional[a,b]-c...A fractional[a,b]-factor of a graph G is a function h from E(G)to[0,1]satisfying a≤d^(h)_(G)(v)≤b for every vertex v of G,where d^(h)_(G)(v)=∑e∈E(v)h(e)and E(v)={e=uv:u∈V(G)}.A graph G is called fractional[a,b]-covered if G contains a fractional[a,b]-factor h with h(e)=1 for any edge e of G.A graph G is called fractional(a,b,k)-critical covered if G—Q is fractional[a,b]-covered for any Q⊆V(G)with∣Q∣=k.In this article,we demonstrate a neighborhood condition for a graph to be fractional(a,b,k)-critical covered.Furthermore,we claim that the result is sharp.展开更多
A path factor of G is a spanning subgraph of G such that its each component is a path.A path factor is called a P≥n-factor if its each component admits at least n vertices.A graph G is called P≥n-factor covered if G...A path factor of G is a spanning subgraph of G such that its each component is a path.A path factor is called a P≥n-factor if its each component admits at least n vertices.A graph G is called P≥n-factor covered if G admits a P≥n-factor containing e for any e∈E(G),which is defined by[Discrete Mathematics,309,2067-2076(2009)].We first define the concept of a(P≥n,k)-factor-critical covered graph,namely,a graph G is called(P≥n,k)-factor-critical covered if G-D is P≥n-factor covered for any D⊆V(G)with|D|=k.In this paper,we verify that(i)a graph G withκ(G)≥k+1 is(P≥2,k)-factor-critical covered if bind(G)>2+k/3;(ii)a graph G with|V(G)|≥k+3 andκ(G)≥k+1 is(P≥3,k)-factor-critical covered if bind(G)≥4+k/3.展开更多
文摘令G是一个有限图,H是G的一个子图.若V(H)=V(G),则称H为G的生成子图.图G的一个λ重F-因子,记为Sλ(F,G),是G的一个生成子图且可分拆为若干与F同构的子图(称为F-区组)的并,使得V(G)中的每一个顶点恰出现在λ个F-区组中.一个图G的λ重F-因子大集,记为LSλ(F G),是G中所有与F同构的子图的一个分拆{B_i}_i,使得每个B_i均构成一个Sλ(F,G).当λ=1时,λ可省略不写.本文中,我们证明了当v≡4 mod 24时,存在LS(K1,3,Kv,v,v).
文摘A graph is said to be K1,3-free if it contains no K1,3 as an induced subgraph. It is shown in this paper that every 2-connected K1,3-free graph contains a connected [2,3]-factor. We also obtain that every connected K1,3-free graph has a spanning tree with maximum degree at most 3.
文摘Let h:E(G)→[0,1]be a function.If a≤∑e∋xh(e)≤b holds for each x∈V(G),then we call G[Fh]a fractional[a,b]-factor of G with indicator function h,where Fh={e:e∈E(G),h(e)>0}.A graph G is called a fractional[a,b]-covered graph if for every edge e of G,there is a fractional[a,b]-factor G[Fh]with h(e)=1.Zhou,Xu and Sun[S.Zhou,Y.Xu,Z.Sun,Degree conditions for fractional(a,b,k)-critical covered graphs,Information Processing Letters 152(2019)105838]defined the concept of a fractional(a,b,k)-critical covered graph,i.e.,for every vertex subset Q with|Q|=k of G,G−Q is a fractional[a,b]-covered graph.In this article,we study the problem of a fractional(2,b,k)-critical covered graph,and verify that a graph G withδ(G)≥3+k is a fractional(2,b,k)-critical covered graph if its toughness t(G)≥1+1b+k2b,where b and k are two nonnegative integers with b≥2+k2.
基金Supported by National Natural Science Foundation of China(Grant No.11371009)
文摘Let a,b,k,r be nonnegative integers with 1 ≤ a ≤b and r ≥ 2. Let G be a graph of order n with n 〉 （a＋b）（r（a＋b）-2）＋ak/a. In this paper, we first show a characterization for all fractional （a, b, k）-critical graphs. Then using the result, we prove that G is all fractional （a, b, k）-critical if δ（G） ≥ （r-1）b2/a ＋k and ｜NG（xl） ∪NG（x2） ∪... ∪NG（xr）｜ ≥ bn＋ak/a＋b for any independent subset {xl, x2, .., xr} in G. Furthermore, it is shown that the lower bound on the condition ｜NG（xl） ∪NG（x2） ∪... ∪NG（xr）｜ ≥ bn=ak/ a＋b is best possible in some sense, and it is an extension of Lu＇s previous result.
基金This work is supported by Six Big Talent Peak of Jiangsu Province,China(Grant No.JY-022).
文摘A fractional[a,b]-factor of a graph G is a function h from E(G)to[0,1]satisfying a≤d^(h)_(G)(v)≤b for every vertex v of G,where d^(h)_(G)(v)=∑e∈E(v)h(e)and E(v)={e=uv:u∈V(G)}.A graph G is called fractional[a,b]-covered if G contains a fractional[a,b]-factor h with h(e)=1 for any edge e of G.A graph G is called fractional(a,b,k)-critical covered if G—Q is fractional[a,b]-covered for any Q⊆V(G)with∣Q∣=k.In this article,we demonstrate a neighborhood condition for a graph to be fractional(a,b,k)-critical covered.Furthermore,we claim that the result is sharp.
基金Supported by Six Big Talent Peak of Jiangsu Province(Grant No.JY–022)333 Project of Jiangsu Provincethe National Natural Science Foundation of China(Grant No.11371009)。
文摘A path factor of G is a spanning subgraph of G such that its each component is a path.A path factor is called a P≥n-factor if its each component admits at least n vertices.A graph G is called P≥n-factor covered if G admits a P≥n-factor containing e for any e∈E(G),which is defined by[Discrete Mathematics,309,2067-2076(2009)].We first define the concept of a(P≥n,k)-factor-critical covered graph,namely,a graph G is called(P≥n,k)-factor-critical covered if G-D is P≥n-factor covered for any D⊆V(G)with|D|=k.In this paper,we verify that(i)a graph G withκ(G)≥k+1 is(P≥2,k)-factor-critical covered if bind(G)>2+k/3;(ii)a graph G with|V(G)|≥k+3 andκ(G)≥k+1 is(P≥3,k)-factor-critical covered if bind(G)≥4+k/3.
