Shi–Shan conjecture for (P2kP1)(P_2\cup kP_1)-free graphs

Let PbP_b denote the path on bb vertices, and let P2kP1P_2\cup kP_1 be the disjoint union of a two-vertex path and kk isolated vertices. A graph is tt-tough if Stc(GS)|S|\geq t\,c(G-S) for every vertex set SS such that GSG-S has at least two components; it is rr-connected if deleting fewer than rr vertices leaves it connected. A graph is (P2kP1)(P_2\cup kP_1)-free if it has no induced subgraph isomorphic to P2kP1P_2\cup kP_1.

Shi–Shan conjecture. Let k4k\geq 4 be an integer and let GG be a 11-tough and 2k2k-connected (P2kP1)(P_2\cup kP_1)-free graph. Then GG is hamiltonian.

The paper proves the analogous assertion with 44-tough in place of 11-tough, so the conjecture proposes that the toughness hypothesis can be weakened. The conjectured 11-tough result remains open in the source.

Sources & referencesView supporting material

Primary source

Lingjuan Shi and Songling Shan, “A note on hamiltonian cycles in 4-tough (P_2kP_1)-free graphs”, arXiv:2202.06192 (2022).

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.