Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
419886 | Discrete Applied Mathematics | 2008 | 7 Pages |
For a fixed multigraph H with vertices w1,…,wmw1,…,wm, a graph G is H-linked if for every choice of vertices v1,…,vmv1,…,vm in G, there exists a subdivision of H in G such that vivi is the branch vertex representing wiwi (for all i ). This generalizes the notions of kk-linked, kk-connected, and kk-ordered graphs.Given a connected multigraph H with kk edges and minimum degree at least two and n⩾7.5kn⩾7.5k, 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)D(H,n) appears to equal the least integer d′d′ such that every n -vertex graph with minimum degree at least d′d′ is b(H)b(H)-connected, where b(H)b(H) is the maximum number of edges in a bipartite subgraph of H.