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


Minimum degree conditions for -linked graphs
Authors:Alexandr Kostochka  Gexin Yu
Institution:aDepartment of Mathematics, University of Illinois, Urbana, IL 61801, USA;bInstitute of Mathematics, Novosibirsk 630090, Russia
Abstract:For a fixed multigraph H with vertices w1,…,wm, a graph G is H-linked if for every choice of vertices v1,…,vm in G, there exists a subdivision of H in G such that vi is the branch vertex representing wi (for all i). This generalizes the notions of k-linked, k-connected, and k-ordered graphs.Given a connected multigraph H with k edges and minimum degree at least two and ngreater-or-equal, slanted7.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) appears to equal the least integer d such that every n-vertex graph with minimum degree at least d is b(H)-connected, where b(H) is the maximum number of edges in a bipartite subgraph of H.
Keywords:Extremal graph problems  Degree conditions  color:black" href="/science?_ob=MathURL&_method=retrieve&_udi=B6TYW-4PGPKN4-1&_mathId=mml16&_user=10&_cdi=5629&_rdoc=19&_acct=C000054348&_version=1&_userid=3837164&md5=a6af6e6cf7569d23331f198d390611ab" title="Click to view the MathML source"  H-linked graphs" target="_blank">alt="Click to view the MathML source">H-linked graphs
本文献已被 ScienceDirect 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

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