Isolated toughness and path-factor uniform graphs
Sizhong Zhou, Zhiren Sun, Hongxia Liu
Abstract
A P ≥ k -factor of a graph G is a spanning subgraph of G whose components are paths of order at least k . We say that a graph G is P ≥ k -factor covered if for every edge e ∈ E ( G ), G admits a P ≥ k -factor that contains e ; and we say that a graph G is P ≥ k -factor uniform if for every edge e ∈ E ( G ), the graph G − e is P ≥ k -factor covered. In other words, G is P ≥ k -factor uniform if for every pair of edges e 1 , e 2 ∈ E ( G ), G admits a P ≥ k -factor that contains e 1 and avoids e 2 . In this article, we testify that (1) a 3-edge-connected graph G is P ≥ k -factor uniform if its isolated toughness I ( G ) > 1; (2) a 3-edge-connected graph G is P ≥ k -factor uniform if its isolated toughness I ( G ) > 2. Furthermore, we explain that these conditions on isolated toughness and edge-connectivity in our main results are best possible in some sense.