Ore-type degree conditions for a graph to be H-linked

✍ Scribed by Alexandr V. Kostochka; Gexin Yu

• Publisher: John Wiley and Sons
• Year: 2008
• Tongue: English
• Weight: 155 KB
• Volume: 58
• Category: Article
• ISSN: 0364-9024
• DOI: 10.1002/jgt.20295

✦ Synopsis

Abstract

Given a fixed multigraph H with V(H) = {h~1~,…, h~m~}, we say that a graph G is H‐linked if for every choice of m vertices v~1~, …, ~v~~m~ in G, there exists a subdivision of H in G such that for every i, v~i~ is the branch vertex representing h~i~. This generalizes the notion of k‐linked graphs (as well as some other notions). For a family ${\cal H}$ of graphs, a graph G is ${\cal H}$‐linked if G is H‐linked for every $H\in {\cal H}$. In this article, we estimate the minimum integer r = r(n, k, d) such that each n‐vertex graph with $\sigma_{2}(G)\ge {r}$ is ${\cal H}$‐linked, where ${\cal H}$ is the family of simple graphs with k edges and minimum degree at least $d \ge 2$. © 2008 Wiley Periodicals, Inc. J Graph Theory 58: 14–26, 2008