Paper detail

Combined degree and connectivity conditions for H-linked graphs

For a given multigraph H, a graph G is H-linked, if |G| \geq |H| and for every injective map τ: V (H) \rightarrow V (G), we can find internally disjoint paths in G, such that every edge from uv in H corresponds to a τ (u) - τ (v) path. To guarantee that a G is H-linked, you need a minimum degree larger than |G|/2. This situation changes, if you know that G has a certain connectivity k. Depending on k, even a minimum degree independent of |G| may suffice. Let δ(k, H, N) be the minimum number, such that every k-connected graph G with |G| = N and δ(G) \geq δ(k, H, N) is H-linked. We study bounds for this quantity. In particular, we find bounds for all multigraphs H with at most three edges, which are optimal up to small additive or multiplicative constants.