Spanning Structures in Multipartite Graph Traversals
Let $G$ be an $r$-partite graph such that the edge density between any two parts is at least $α$. We consider the problem of determining how large $α$ must be in order to guarantee that $G$ has a Hamiltonian traversal (an $r$-cycle subgraph containing exactly one vertex from each part), and show that this critical density tends to $\frac 1 2$ as $r$ increases. This resolves a conjecture of Badakhshian, Falgas-Ravry, and Sharifzadeh. We also study the critical densities necessary to guarantee the existence of other spanning structures in traversals, particularly subgraph factors, and obtain…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2608.15005
curl -X POST /api/v1/records/arxiv/2608.15005/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2608.15005/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'