For a given multigraph H, a graph G is H-linked, if |G| \geq |H| and for every injective map { \tau}: V (H) \rightarrow V (G), we can find internally disjoint paths in G, such that every edge from uv in H corresponds to a { \tau} (u) - { \tau} (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 { \delta}(k, H, N) be the minimum number, such that every k-connected graph G with |G| = N and { \delta}(G) \geq { \delta}(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.
Categories: math.CO