2023/04/03 by Zhou, Sizhong, Liu, Hongxia
#05C38 #05C70 #90B10 #Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2304.00937
A spanning subgraph F of G is called a path factor if every component of F is a path of order at least 2. Let k≥2 be an integer. A P≥ k-factor of G means a path factor in which every component has at least k vertices. A graph G is called a P≥ k-factor avoidable graph if for any e∈ E(G), G has a P≥ k-factor avoiding e. A graph G is called a (P≥ k,n)-factor critical avoidable graph if for any W⊆ V(G) with |W|=n, G-W is a P≥ k-factor avoidable graph. In other words, G is (P≥ k,n)-factor critical avoidable if for any W⊆ V(G) with |W|=n and any e∈ E(G-W), G-W-e admits a P≥ k-factor. In this article, we verify that (\romannumeral1) an (n+r+2)-connected graph G is (P≥2,n)-factor critical avoidable if I(G)>(n+r+3)/(2(r+2)); (\romannumeral2) an (n+r+2)-connected graph G is (P≥3,n)-factor critical avoidable if t(G)>(n+r+2)/(2(r+2)); (\romannumeral3) an (n+r+2)-connected graph G is (P≥3,n)-factor critical avoidable if I(G)>(n+3(r+2))/(2(r+2)); where n and r are two nonnegative integers.