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, .展开更多
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.展开更多
Let a,b and k be nonnegative integers with a≥2 and b≥a(k+1)+2.A graph G is called a k-Hamiltonian graph if after deleting any k vertices of G the remaining graph of G has a Hamiltonian cycle.A graph G is said to hav...Let a,b and k be nonnegative integers with a≥2 and b≥a(k+1)+2.A graph G is called a k-Hamiltonian graph if after deleting any k vertices of G the remaining graph of G has a Hamiltonian cycle.A graph G is said to have a k-Hamiltonian[a,b]-factor if after deleting any k vertices of G the remaining graph of G admits a Hamiltonian[a,b]-factor.Let G is a k-Hamiltonian graph of order n with n≥a+k+2.In this paper,it is proved that G contains a k-Hamiltonian[a,b]-factor ifδ(G)≥a+k andδ(G)≥I(G)≥a-1+(a(k+1))/(b-2).展开更多
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...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 result.展开更多
Let a,b,k be nonnegative integers with 2≤a<b.A graph G is called a k-Hamiltonian graph if G-U contains a Hamiltonian cycle for any subset U?V(G)with|U|=k.An[a,b]-factor F of G is called a Hamiltonian[a,b]-factor i...Let a,b,k be nonnegative integers with 2≤a<b.A graph G is called a k-Hamiltonian graph if G-U contains a Hamiltonian cycle for any subset U?V(G)with|U|=k.An[a,b]-factor F of G is called a Hamiltonian[a,b]-factor if F contains a Hamiltonian cycle.If G-U admits a Hamiltonian[a,b]-factor for any subset U?V(G)with|U|=k,then we say that G has a k-Hamiltonian[a,b]-factor.Suppose that G is a k-Hamiltonian graph of order n with n≥((a+b-4)(2 a+b+k-6))/(b-2)+k andδ(G)≥a+k.In this paper,it is proved that G admits a k-Hamiltonian[a,b]-factor if max{dG(x),dG(y)}≥((a-2)n+(b-2)k)/(a+b-4)+2 for each pair of nonadjacent vertices x and y in G.展开更多
文摘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 the National Natural Science Foundation of China (Grant No. 11371009)the National Social Science Foundation of China (Grant No. 14AGL001)+1 种基金sponsored by Six Big Talent Peak of Jiangsu Province (Grant No. JY–022)333 Project of Jiangsu Province
文摘Let a,b and k be nonnegative integers with a≥2 and b≥a(k+1)+2.A graph G is called a k-Hamiltonian graph if after deleting any k vertices of G the remaining graph of G has a Hamiltonian cycle.A graph G is said to have a k-Hamiltonian[a,b]-factor if after deleting any k vertices of G the remaining graph of G admits a Hamiltonian[a,b]-factor.Let G is a k-Hamiltonian graph of order n with n≥a+k+2.In this paper,it is proved that G contains a k-Hamiltonian[a,b]-factor ifδ(G)≥a+k andδ(G)≥I(G)≥a-1+(a(k+1))/(b-2).
基金supported by Natural Sciences and Engineering Research Council of Canada (Grant No. 144073)Shandong University Visiting Scholar FundPCSIRT Project of the Ministry of Education of China
文摘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 result.
基金supported by the National Natural Science Foundation of China(Grant No.11371009)the National Social Science Foundation of China(Grant No.14AGL001)+1 种基金sponsored by Six Big Talent Peak of Jiangsu Province(Grant No.JY–022)333 Project of Jiangsu Province。
文摘Let a,b,k be nonnegative integers with 2≤a<b.A graph G is called a k-Hamiltonian graph if G-U contains a Hamiltonian cycle for any subset U?V(G)with|U|=k.An[a,b]-factor F of G is called a Hamiltonian[a,b]-factor if F contains a Hamiltonian cycle.If G-U admits a Hamiltonian[a,b]-factor for any subset U?V(G)with|U|=k,then we say that G has a k-Hamiltonian[a,b]-factor.Suppose that G is a k-Hamiltonian graph of order n with n≥((a+b-4)(2 a+b+k-6))/(b-2)+k andδ(G)≥a+k.In this paper,it is proved that G admits a k-Hamiltonian[a,b]-factor if max{dG(x),dG(y)}≥((a-2)n+(b-2)k)/(a+b-4)+2 for each pair of nonadjacent vertices x and y in G.
