On Minimum Degree Implying That a Graph is H‐Linked
Ronald J. Gould, Alexandr V. Kostochka, Gexin Yu · SIAM Journal on Discrete Mathematics · 2006
Given a fixed multigraph H, possibly containing loops, with $V(H) = \{h_1,\ldots,h_m\}$, we say that a graph G is H‐linked if for every choice of m vertices $v_1,\ldots,v_m$ in G, there exists a subdivision of H in G such that $v_i$ is the branch vertex representing $h_i$ (for all i). This generalizes the concept of k‐linked graphs (as well as a number of other well‐known path or cycle properties). In this paper we determine a sharp lower bound on $\delta(G)$ (which depends upon H) such that each graph G on at least $10(|V(H)|+|E(H)|)$ vertices satisfying this bound is H‐linked.