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 n7.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 等数据库收录! |
|