Article ID Journal Published Year Pages File Type
419886 Discrete Applied Mathematics 2008 7 Pages PDF
Abstract

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.

Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Authors
, ,