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).展开更多
A spanning subgraph F of a graph G is called a path factor of G if each component of F is a path.A P≥k-factor means a path factor with each component having at least k vertices,where k≥2 is an integer.Bazgan,Benhamd...A spanning subgraph F of a graph G is called a path factor of G if each component of F is a path.A P≥k-factor means a path factor with each component having at least k vertices,where k≥2 is an integer.Bazgan,Benhamdine,Li and Wozniak[C.Bazgan,A.H.Benhamdine,H.Li,M.Wozniak,Partitioning vertices of 1-tough graph into paths,Theoret.Comput.Sci.263(2001)255–261.]obtained a toughness condition for a graph to have a P≥3-factor.We introduce the concept of a P≥k-factor deleted graph,that is,if a graph G has a P≥k-factor excluding e for every e∈E(G),then we say that G is a P≥k-factor deleted graph.In this paper,we show four sufficient conditions for a graph to be a P≥3-factor deleted graph.Furthermore,it is shown that four results are 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 Six Talent Peaks Project in Jiangsu Province,China(Grant No.JY–022)。
文摘A spanning subgraph F of a graph G is called a path factor of G if each component of F is a path.A P≥k-factor means a path factor with each component having at least k vertices,where k≥2 is an integer.Bazgan,Benhamdine,Li and Wozniak[C.Bazgan,A.H.Benhamdine,H.Li,M.Wozniak,Partitioning vertices of 1-tough graph into paths,Theoret.Comput.Sci.263(2001)255–261.]obtained a toughness condition for a graph to have a P≥3-factor.We introduce the concept of a P≥k-factor deleted graph,that is,if a graph G has a P≥k-factor excluding e for every e∈E(G),then we say that G is a P≥k-factor deleted graph.In this paper,we show four sufficient conditions for a graph to be a P≥3-factor deleted graph.Furthermore,it is shown that four results are best possible in some sense.
