{"id":"arxiv/2608.15005","url":"https://arxiv.org/abs/2608.15005","tags":["math.CO"],"score":0,"title":"Spanning Structures in Multipartite Graph Traversals","domain":"math.CO","source":"arxiv","authors":["Isabel McGuigan"],"reviews":0,"subject":"math.CO","summary":"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…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-08-15","reactions":{}}