Mathematicians solve graph puzzle with real-world network implications
Researchers have cracked a foundational problem in network design: determining how densely connected a network must be to guarantee it contains optimal routing paths. The findings could improve everything from telecommunications infrastructure to supply chain logistics by clarifying minimum connectivity requirements.
Originaltitel: On density conditions for transversal trees in multipartite graphs
<p>Let <em>G </em>be an <em>r</em>-partite graph such that the edge density between any two parts is at least<em> α</em>. How large does <em>α</em> need to be to guarantee that <em>G</em> contains a connected transversal, that is, a tree on <em>r</em> vertices meeting each part in one vertex? And what if instead we want to guarantee the existence of a Hamiltonian transversal? In this paper we initiate the study of such extremal multipartite graph problems, obtaining a number of results and providing many new constructions, conjectures and further questions.</p>