Path-factor critical covered graphs and path-factor uniform graphs
Jie Yu Wu · RAIRO - Operations Research · 2022
A path-factor in a graphGis a spanning subgraphFofGsuch that every component ofFis a path. Letdandnbe two nonnegative integers withd ≥ 2. AP≥d-factor ofGis its spanning subgraph each of whose components is a path with at leastdvertices. A graphGis called aP≥d-factor covered graph if for anye ∈ E(G),Gadmits aP≥d-factor containinge. A graphGis called a (P≥d, n)-factor critical covered graph if for anyN ⊆ V(G) with |N| =n, the graphG − Nis aP≥d-factor covered graph. A graphGis called aP≥d-factor uniform graph if for anye ∈ E(G), the graphG − eis aP≥d-factor covered graph. In this paper, we verify the following two results: (i) An (n + 1)-connected graphGof order at leastn + 3 is a (P≥3, n)-factor critical covered graph ifGsatisfiesδ(G) > (α(G)+2n+3)/2; (ii) Every regular graphGwith degreer ≥ 2 is aP≥3-factor uniform graph.