2012/06/07 by Florian Pfender, Pfender, Florian
Computer Science · Mathematics · #05C40 #Advanced Graph Theory Research #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #FOS: Mathematics #Interconnection Networks and Systems #math.CO #msc:05C40
paper · pdf · doi:10.48550/arxiv.1206.1427
arxiv created 2012/06/07 · openalex publication_date 2012/06/07 · arxiv updated 2012/06/08 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
For a given multigraph H, a graph G is H-linked, if |G| ≥ |H| and for every injective map τ: V (H) → 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) ≥ δ(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.