Shi–Shan's toughness conjecture for forbidden linear forests

Let k4k\ge 4 be an integer. A graph is tt-tough if its toughness satisfies τ(G)t\tau(G)\ge t, a graph is rr-connected if deleting fewer than rr vertices leaves it connected, and PnP_n denotes the path on nn vertices; kP1kP_1 is the disjoint union of kk isolated vertices. A graph is (P2kP1)(P_2\cup kP_1)-free if it has no induced subgraph consisting of a two-vertex path together with kk isolated vertices. Shi–Shan's conjecture. Let GG be a 11-tough and 2k2k-connected (P2kP1)(P_2\cup kP_1)-free graph. Then GG is hamiltonian. This conjecture is a strengthening of the general toughness conjecture for Hamiltonicity in a structured graph class. It has been independently confirmed by Xu, Li, and Zhou, and by Ota and Sanka.

Sources & referencesView supporting material

Primary source

Feng Liu, “Every 2k-connected (P_2kP_1)-free graph with toughness greater than one is hamiltonian-connected”, arXiv:2503.12860 (2025).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.