2023/05/08 by Hui Qin, Guowei Dai, Qin, Hui +7
Computer Science · Mathematics · #05C38 #05C70 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Interconnection Networks and Systems #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.2305.04713
openalex publication_date 2023/05/08 · openalex created_date 2023/05/12 · openalex updated_date 2026/07/28
A spanning subgraph H of a graph G is called a P≥ k-factor of G if every component of H is isomorphic to a path of order at least k, where k≥2 is an integer. A graph G is called a (P≥ k,l)-factor critical graph if G-V' contains a P≥ k-factor for any V'⊆ V(G) with |V'|=l. A graph G is called a (P≥ k,m)-factor deleted graph if G-E' has a P≥ k-factor for any E'⊆ E(G) with |E'|=m. Intuitively, if a graph is dense enough, it will have a P≥ 3-factor. In this paper, we give some sufficient conditions for a graph to be a (P≥ 3,l)-factor critical graph or a (P≥ 3,m)-factor deleted graph. In this paper, we demonstrate that (i) G is a (P≥ 3,l)-factor critical graph if its sun toughness s(G)>(l+1)/(3) and κ(G)≥ l+2. (ii) G is a (P≥ 3,l)-factor critical graph if its degree sum σ3(G)≥ n+2l and κ(G)≥ l+1. (iii) G is a (P≥ 3,m)-factor deleted graph if its sun toughness s(G)≥ (m+1)/(m+2) and κ(G)≥ 2m+1. (iv) G is a (P≥ 3,m)-factor deleted graph if its degree sum σ3(G)≥ n+2m and κ(G)≥ 2m+1.