An infinite family of bipartite hypotraceable graphs
Source: arxiv.org/abs/2611.23018
A graph is hypotraceable if it has no Hamiltonian path but every vertex-deleted subgraph does. In 1978, Grötschel asked whether a bipartite hypotraceable graph exists. We resolve this long-standing question in a strong sense by proving that such graphs exist for every sufficiently large even order. Moreover, we show that bipartite hypotraceable graphs can have $\left(1/4+o(1)\right)n^2$ edges, asymptotically attaining the maximum possible number of edges of a bipartite graph, and that there are at least $2^{(1/4+o(1))n^2}$ nonisomorphic examples of order $n$, as $n$ tends to infinity through…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2611.23018
curl -X POST /api/v1/records/arxiv/2611.23018/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2611.23018/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'