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

Research output: Contribution to journalArticlepeer-review

Abstract

Given a fixed multigraph H with V(H) = {h1,..., hm}, we say that a graph G is H-linked if for every choice of m vertices v 1,..., vm in G, there exists a subdivision of H in G such that for every i, vi, is the branch vertex representing h i. This generalizes the notion of k-linked graphs (as well as some other notions). For a family H of graphs, a graph G is H-linked if G is H-linked for every H ∈ H. In this article, we estimate the minimum integer r=r(n,k,d) such that each n-vertex graph with σ2(G)≥r is H-linked, where H is the family of simple graphs with k edges and minimum degree at least d≥2.

Original languageEnglish (US)
Pages (from-to)14-26
Number of pages13
JournalJournal of Graph Theory
Volume58
Issue number1
DOIs
StatePublished - May 2008

Keywords

  • H-linked
  • Ore-type degree condition

ASJC Scopus subject areas

  • Geometry and Topology
  • Discrete Mathematics and Combinatorics

Fingerprint

Dive into the research topics of 'Ore-type degree conditions for a graph to be H-linked'. Together they form a unique fingerprint.

Cite this