کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
419886 683871 2008 7 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Minimum degree conditions for HH-linked graphs
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Minimum degree conditions for HH-linked graphs
چکیده انگلیسی

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.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 156, Issue 9, 1 May 2008, Pages 1542–1548
نویسندگان
, ,