## 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 v_{1},..., v_{m} in G, there exists a subdivision of H in G such that v_{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.

Original language | English (US) |
---|---|

Pages (from-to) | 321-339 |

Number of pages | 19 |

Journal | Journal of Graph Theory |

Volume | 50 |

Issue number | 4 |

DOIs | |

State | Published - Dec 2005 |

## ASJC Scopus subject areas

- Geometry and Topology