An extremal problem for H-linked graphs

✍ Scribed by Alexandr Kostochka; Gexin Yu

• Publisher: John Wiley and Sons
• Year: 2005
• Tongue: English
• Weight: 167 KB
• Volume: 50
• Category: Article
• ISSN: 0364-9024
• DOI: 10.1002/jgt.20115

✦ Synopsis

Abstract

We introduce the notion of H‐linked graphs, where H is a fixed multigraph with vertices w~1~,…,w~m~. A graph G is H‐linked if for every choice of vertices υ~1~,…, υ~m~ in G, there exists a subdivision of H in G such that υ~i~ is the branch vertex representing w~i~ (for all i). This generalizes the notions of k‐linked, k‐connected, and k‐ordered graphs. Given k and n ≥ 5k+6, we determine the least integer d such that, for every loopless graph H with k edges and minimum degree at least two, every n‐vertex graph with minimum degree at least d is H‐linked. This value D~1~(k,n) appears to equal the least integer d′ such that every n‐vertex graph with minimum degree at least d′ is k‐connected. On the way to the proof, we extend a theorem by Kierstead et al. on the least integer d˝ such that every n‐vertex graph with minimum degree at least d˝ is k‐ordered. © 2005 Wiley Periodicals, Inc.