Path-factor critical covered graphs and path-factor uniform graphs

School of Economics and management, Jiangsu University of Science and Technology, Zhenjiang, Jiangsu 212100, P.R. China

^* Corresponding author: jskjdxwj@126.com

Received: 18 May 2022
Accepted: 24 November 2022

Abstract

A path-factor in a graph G is a spanning subgraph F of G such that every component of F is a path. Let d and n be two nonnegative integers with d ≥ 2. A P_≥d-factor of G is its spanning subgraph each of whose components is a path with at least d vertices. A graph G is called a P_≥d-factor covered graph if for any e ∈ E(G), G admits a P_≥d-factor containing e. A graph G is called a (P_≥d, n)-factor critical covered graph if for any N ⊆ V(G) with |N| = n, the graph G − N is a P_≥d-factor covered graph. A graph G is called a P_≥d-factor uniform graph if for any e ∈ E(G), the graph G − e is a P_≥d-factor covered graph. In this paper, we verify the following two results: (i) An (n + 1)-connected graph G of order at least n + 3 is a (P_≥3, n)-factor critical covered graph if G satisfies δ(G) > (α(G)+2n+3)/2; (ii) Every regular graph G with degree r ≥ 2 is a P_≥3-factor uniform graph.