Shi and Shan's conjecture for tough connected (P2kP1)(P_2\cup kP_1)-free graphs

Let kk be an integer with k4k\ge 4, and let GG be a graph. Here PnP_n denotes the path on nn vertices, P2kP1P_2\cup kP_1 is the disjoint union of a two-vertex path and kk isolated vertices, a graph is 11-tough when its toughness is at least 11, and 2k2k-connected when deleting fewer than 2k2k vertices leaves it connected. The graph is (P2kP1)(P_2\cup kP_1)-free if it has no induced subgraph isomorphic to P2kP1P_2\cup kP_1. Shi and Shan's conjecture. Every 11-tough, 2k2k-connected (P2kP1)(P_2\cup kP_1)-free graph is Hamiltonian. Shi and Shan had proved the analogous statement with 44-toughness for k4k\ge4; the conjecture weakens the toughness requirement to 11 and remains open in the supplied source.

Sources & referencesView supporting material

Primary source

Leyou Xu, Chengli Li and Bo Zhou, “Hamiltonicity of 1-tough (P_2kP_1)-free graphs”, arXiv:2303.09741 (2023).

Additional references

2 papers in this index state this conjecture (2022–2023). The statement above is taken from the most recent of them; the others are arXiv:2210.10408.

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.