Characterizing path-factor uniform graphs with respect to the degree sum of non-adjacent vertices

College of Science, University of Shanghai for Science and Technology, Shanghai 200093, P.R. China

^* Corresponding author: mathzhangping@126.com

Received: 27 November 2024
Accepted: 23 October 2025

Abstract

For a graph G and a set H of connected graphs, an H-factor of G is a spanning subgraph of G with each component isomorphic to some member in H. If each component of H is isomorphic to a path, then we call the H-factor a path-factor. For each integer k ≥ 2, a graph G is P_≥k-factor uniform if for any two distinct edges e₁ and e₂, G admits a P_≥k-factor including e₁ and excluding e₂. In this note, we determine two lower bounds on the degree sum of non-adjacent vertices to ensure that G is P_≥k-factor uniform for k = 2 and k = 3. Furthermore, we construct some extremal graphs to show that the bounds are best possible. The results improve some known results slightly.