On P≥3-factor Deleted Graphs

• 作者: Si-zhong ZHOU Zhi-ren SUN Hong-xia LIU
• 来源期刊: 应用数学学报（英文版）
• 年，卷（期）: 2022,（1）
• 页码范围: 178-186
• 页数: 9页
• 语种: 英文

摘要

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.