首页 | 本学科首页   官方微博 | 高级检索  
     检索      


On large semi-linked graphs
Authors:Alexander Halperin  Colton Magnant  Hua Wang
Institution:1. Department of Mathematics and Computer Science, Salisbury University, 1101 Camden Ave., Salisbury, MD 21804, United States;2. Department of Mathematical Sciences, Georgia Southern University, 65 Georgia Ave., Room 3008, P.O. Box 8093, Statesboro, GA 30460, United States
Abstract:Let HH be a multigraph, possibly with loops, and consider a set S⊆V(H)SV(H). A (simple) graph GG is (H,S)(H,S)-semi-linked   if, for every injective map f:S→V(G)f:SV(G), there exists an injective map g:V(H)?S→V(G)?f(S)g:V(H)?SV(G)?f(S) and a set of |E(H)||E(H)| internally disjoint paths in GG connecting pairs of vertices of  f(S)∪g(V(H)?S)f(S)g(V(H)?S) for every edge between the corresponding vertices of HH. This new concept of (H,S)(H,S)-semi-linkedness is a generalization of HH-linkedness  . We establish a sharp minimum degree condition for a sufficiently large graph GG to be (H,S)(H,S)-semi-linked.
Keywords:Graph linkedness  Minimum degree
本文献已被 ScienceDirect 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号