کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
419886 | 683871 | 2008 | 7 صفحه PDF | دانلود رایگان |

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.
Journal: Discrete Applied Mathematics - Volume 156, Issue 9, 1 May 2008, Pages 1542–1548