A path-factor is a spanning subgraph F of G such that every component of F is a path with at least two vertices.Let k≥2 be an integer.A P_(≥k)-factor of G means a path factor in which each component is a path with a...A path-factor is a spanning subgraph F of G such that every component of F is a path with at least two vertices.Let k≥2 be an integer.A P_(≥k)-factor of G means a path factor in which each component is a path with at least k vertices.A graph G is a P_(≥k)-factor covered graph if for any e∈E(G),G has a P_(≥k)-factor including e.Letβbe a real number with 1/3≤β≤1 and k be a positive integer.We verify that(ⅰ)a k-connected graph G of order n with n≥5k+2 has a P_(≥3)-factor if|NG(I)|>β(n-3k-1)+k for every independent set I of G with|I|=「β(2k+1)」;(ⅱ)a(k+1)-connected graph G of order n with n≥5k+2 is a P_(≥3)-factor covered graph if|NG(I)|>β(n-3k-1)+k+1 for every independent set I of G with|I|=「β(2k+1)」.展开更多
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.展开更多
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.展开更多
文摘A path-factor is a spanning subgraph F of G such that every component of F is a path with at least two vertices.Let k≥2 be an integer.A P_(≥k)-factor of G means a path factor in which each component is a path with at least k vertices.A graph G is a P_(≥k)-factor covered graph if for any e∈E(G),G has a P_(≥k)-factor including e.Letβbe a real number with 1/3≤β≤1 and k be a positive integer.We verify that(ⅰ)a k-connected graph G of order n with n≥5k+2 has a P_(≥3)-factor if|NG(I)|>β(n-3k-1)+k for every independent set I of G with|I|=「β(2k+1)」;(ⅱ)a(k+1)-connected graph G of order n with n≥5k+2 is a P_(≥3)-factor covered graph if|NG(I)|>β(n-3k-1)+k+1 for every independent set I of G with|I|=「β(2k+1)」.
基金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.
基金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.
