Toughness Bounds for Fractional Hamiltonicity and Resistance Positivity
A graph is fractionally Hamiltonian if it admits a nonnegative edge weighting in $[0,1]$ of total weight equal to its order such that every nontrivial edge cut has weight at least two. Motivated by Chvátal's Toughness Conjecture, Scheinerman and Ullman conjectured that every $2$-tough graph is fractionally Hamiltonian. In this paper, we show that every connected graph on at least three vertices that is not fractionally Hamiltonian has a non-Hamiltonian chordal spanning supergraph. Since adding edges does not decrease toughness, a theorem of Kabela and Kaiser that every $10$-tough chordal…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2609.03412
curl -X POST /api/v1/records/arxiv/2609.03412/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2609.03412/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'