Spanning $H$-subdivisions with Prescribed Path Lengths

Abstract

We study spanning $H$-subdivisions in dense graphs where the length of every subdivision path is prescribed in advance. This problem is motivated in part by a question of Pavez-Signé [Combin. Probab. Comput. 33 (2024), 121--128], who asked whether the subdivision paths in a spanning $H$-subdivision can be required to have similar lengths. Let $h\ge 3$ be an integer and let $0<\beta \ll \alpha \ll 1/h$. We prove that, for all sufficiently large $n$, every $n$-vertex graph $G$ with $\delta (G)\ge n/2+\lfloor h/3\rfloor$ has the following property. For every graph $H$ with $h$ edges and no isolated vertices, write $E(H)=\{e_1,\dots ,e_h\}$, and every choice of integers ${\ell }_1,\dots ,{\ell }_h\ge 4$ satisfying ${\sum }_{i=1}^h{\ell }_i=n-|V(H)|+h$ and ${\sum }_{{\ell }_i<\alpha n}{\ell }_i\le \beta n$, the graph $G$ contains a spanning $H$-subdivision in which the $i$th edge of $H$ is replaced by a path of length exactly ${\ell }_i$. We also give a family of examples showing that a linear additive term in $h$ is necessary in general.

28 pages, 1 figure