Implications among linkage properties in graphs

Given a graph H with vertices w 1 , …, w m , a graph G with at least m vertices is H ‐ linked if for every choice of vertices v 1 , …, 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 1 and H 2 with the same order that are not contained in stars, the property of being H 1 ‐linked implies that of being H 2 ‐linked if and only if H 2 ⊆ H 1 . The implication also holds when H 1 is obtained from H 2 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