Let a, b, r be nonnegative integers with 1 ≤ a ≤ b and r ≥ 2. Let G be a graph of order n with n 〉（a＋2 b）（r（a＋b）-2）/b.In this paper, we prove that G is fractional ID-[a, b]-factor-critical if δ（G）≥bn/a...Let a, b, r be nonnegative integers with 1 ≤ a ≤ b and r ≥ 2. Let G be a graph of order n with n 〉（a＋2 b）（r（a＋b）-2）/b.In this paper, we prove that G is fractional ID-[a, b]-factor-critical if δ（G）≥bn/a＋2 b＋a（r-1）and ｜NG（x1） ∪ NG（x2） ∪…∪ NG（xr）｜ ≥（a＋b）n/（a＋2 b） for any independent subset {x1,x2,…,xr} in G. It is a generalization of Zhou et al.＇s previous result [Discussiones Mathematicae Graph Theory, 36： 409-418（2016）]in which r = 2 is discussed. Furthermore, we show that this result is best possible in some sense.展开更多
A graph G is called a (g, f)-uniform graph if for each edge of G, there is a(g, f)-factor containing it and another (g, f)-factor excluding it. In this paper a necessary andsufficient condition for a graph to be a (g,...A graph G is called a (g, f)-uniform graph if for each edge of G, there is a(g, f)-factor containing it and another (g, f)-factor excluding it. In this paper a necessary andsufficient condition for a graph to be a (g, f)-uniform graph is given and some applications of thiscondition are discussed. In particular, some simple sufficient conditions for a graph to be an [a,b]-uniform graph are obtained for a b.展开更多
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.展开更多
1 Introduction The graphs considered in this note will be finite undirected graphs which have nomuliple edges or loops. Let G be a graph with a vertex set V(G) and edge set E(G).For a vertex x of G the degree of x in ...1 Introduction The graphs considered in this note will be finite undirected graphs which have nomuliple edges or loops. Let G be a graph with a vertex set V(G) and edge set E(G).For a vertex x of G the degree of x in G is denoted by d_G(x). Let g and f be two in-teger-valued functions defined on V(G) such that g(x)≤f(x) for every x∈V(G). Then a(g,f)-factor of G is a spanning subgraph H of G satisfying g(x)≤d_H(x)≤f(x) for展开更多
Let G be a graph of order n, and let a and b be integers, such that 1 ≤ a b. Let H be a subgraph of G with m(≤b) edges, and δ(G) be the minimum degree. We prove that G has a [a,b]-factor containing all edges of H i...Let G be a graph of order n, and let a and b be integers, such that 1 ≤ a b. Let H be a subgraph of G with m(≤b) edges, and δ(G) be the minimum degree. We prove that G has a [a,b]-factor containing all edges of H if , , and when a ≤ 2, .展开更多
基金supported by the National Natural Science Foundation of China(Nos.11371052,11731002)the Fundamental Research Funds for the Central Universities(Nos.2016JBM071,2016JBZ012)the 111 Project of China(B16002)
文摘Let a, b, r be nonnegative integers with 1 ≤ a ≤ b and r ≥ 2. Let G be a graph of order n with n 〉（a＋2 b）（r（a＋b）-2）/b.In this paper, we prove that G is fractional ID-[a, b]-factor-critical if δ（G）≥bn/a＋2 b＋a（r-1）and ｜NG（x1） ∪ NG（x2） ∪…∪ NG（xr）｜ ≥（a＋b）n/（a＋2 b） for any independent subset {x1,x2,…,xr} in G. It is a generalization of Zhou et al.＇s previous result [Discussiones Mathematicae Graph Theory, 36： 409-418（2016）]in which r = 2 is discussed. Furthermore, we show that this result is best possible in some sense.
基金Supported by National Natural Science Foundation (10471078, 10201019) and RSDP (20040422004) of China
文摘A graph G is called a (g, f)-uniform graph if for each edge of G, there is a(g, f)-factor containing it and another (g, f)-factor excluding it. In this paper a necessary andsufficient condition for a graph to be a (g, f)-uniform graph is given and some applications of thiscondition are discussed. In particular, some simple sufficient conditions for a graph to be an [a,b]-uniform graph are obtained for a b.
文摘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.
基金Project supported by the National Natural Science Foundation of China and Doctoral Discipline Foundation.
文摘1 Introduction The graphs considered in this note will be finite undirected graphs which have nomuliple edges or loops. Let G be a graph with a vertex set V(G) and edge set E(G).For a vertex x of G the degree of x in G is denoted by d_G(x). Let g and f be two in-teger-valued functions defined on V(G) such that g(x)≤f(x) for every x∈V(G). Then a(g,f)-factor of G is a spanning subgraph H of G satisfying g(x)≤d_H(x)≤f(x) for
文摘Let G be a graph of order n, and let a and b be integers, such that 1 ≤ a b. Let H be a subgraph of G with m(≤b) edges, and δ(G) be the minimum degree. We prove that G has a [a,b]-factor containing all edges of H if , , and when a ≤ 2, .
