## Abstract

For a fixed multigraph H 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 a connected multigraph H with k edges and minimum degree at least two and n ≥ 7.5 k, we determine the least integer d such that every n-vertex simple graph with minimum degree at least d is H-linked. This value D (H, n) appears to equal the least integer d^{′} such that every n-vertex graph with minimum degree at least d^{′} is b (H)-connected, where b (H) is the maximum number of edges in a bipartite subgraph of H.

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

Pages (from-to) | 1542-1548 |

Number of pages | 7 |

Journal | Discrete Applied Mathematics |

Volume | 156 |

Issue number | 9 |

DOIs | |

State | Published - May 1 2008 |

## Keywords

- Degree conditions
- Extremal graph problems
- H-linked graphs

## ASJC Scopus subject areas

- Discrete Mathematics and Combinatorics
- Applied Mathematics