Implications among linkage properties in graphs

Given a graph H with vertices w₁, …, w_m, a graph G with at least m vertices is H‐linked if for every choice of vertices v₁, …, v_m in G, there is a subdivision of H in G such that v_i is the branch vertex representing w_i (for all i ). This concept generalizes the notions of k‐linked, k‐connected, and k‐ordered graphs. For graphs H₁ and H₂ with the same order that are not contained in stars, the property of being H₁‐linked implies that of being H₂‐linked if and only if H₂?H₁. The implication also holds when H₁ is obtained from H₂ by replacing an edge xy with an edge from y to a new vertex x′. Other instances of nonimplication are obtained, using a lemma that the number of vertices appearing in minimum vertex covers of a graph G is at most the vertex cover number plus the size of a maximum matching. © 2009 Wiley Periodicals, Inc. J Graph Theory 60: 327‐337, 2009