Tight toughness variant condition for fractional k-factors
Wei Dong Gao, Weifan Wang, Yaojun Chen · Ars Mathematica Contemporanea · 2024
The toughness t(G) of graph G is formalized as the minimum ratio of |S| and ω(G − S) over all vertex subsets S subject to ω(G − S) > 1. As the unique variant parameter of toughness, τ(G) is formulated as the minimum ratio of |S| and ω(G − S) − 1 traversing all the vertex subset S restricted to ω(G − S) ≥ 2. The extant contributions reveal that there is a substantial correlation between toughness and fractional factors. However, there is still a paucity of solid studies on toughness variants τ(G). This work provides several theoretical underpinnings for the tight toughness variant bound for a graph G which admits a fractional k-factor. To be specific, a graph G has a fractional k-factor if τ(G) > k for k ≥ 3 and if τ(G)>3/2 for k = 2. The sharpness of the given bounds is explained by counterexamples.