Isolated toughness and path-factor uniform graphs

¹ School of Science, Jiangsu University of Science and Technology, Zhenjiang, Jiangsu 212100, P.R. China
² School of Mathematical Sciences, Nanjing Normal University, Nanjing, Jiangsu 210046, P.R. China
³ School of Mathematics and Informational Science, Yantai University, Yantai, Shandong 264005, P.R. China

^* Corrresponding author: zsz_cumt@163.com

Received: 17 December 2019
Accepted: 11 April 2021

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₁, e₂ ∈ E(G), G admits a P_≥k-factor that contains e₁ and avoids e₂. 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.