Premium
Implications among linkage properties in graphs
Author(s) -
Liu Qi,
West Douglas B.,
Yu Gexin
Publication year - 2009
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.20362
Subject(s) - combinatorics , mathematics , vertex (graph theory) , graph , neighbourhood (mathematics) , discrete mathematics , mathematical analysis
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