An improved bound for the intersection of two longest cycles in $k$-connected graphs
Source: arxiv.org/abs/2611.07145
A conjecture attributed to Smith states that in every $k$-connected graph, every pair of longest cycles intersects in at least $k$ vertices. We prove that every two longest cycles in a $k$-connected graph on $n$ vertices intersect in at least $\min\{k,10k-n-30\}$ vertices. Consequently, Smith's conjecture holds whenever $k\ge \frac{n+30}{9}$. This improves the previous bound of $\frac{n+16}{7}$ for $n>33$ and also implies a bound of $\frac{n+22}{9}$ for paths instead of cycles.
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2611.07145
curl -X POST /api/v1/records/arxiv/2611.07145/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2611.07145/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'