Isolated toughness and path-factor uniform graphs
Sizhong Zhou, Zhiren Sun, Hongxia Liu · RAIRO - Operations Research · 2021
AP≥k-factor of a graphGis a spanning subgraph ofGwhose components are paths of order at leastk. We say that a graphGisP≥k-factor covered if for every edgee∈E(G),Gadmits aP≥k-factor that containse; and we say that a graphGisP≥k-factor uniform if for every edgee∈E(G), the graphG−eisP≥k-factor covered. In other words,GisP≥k-factor uniform if for every pair of edgese1,e2∈E(G),Gadmits aP≥k-factor that containse1and avoidse2. In this article, we testify that (1) a 3-edge-connected graphGisP≥k-factor uniform if its isolated toughnessI(G) > 1; (2) a 3-edge-connected graphGisP≥k-factor uniform if its isolated toughnessI(G) > 2. Furthermore, we explain that these conditions on isolated toughness and edge-connectivity in our main results are best possible in some sense.