Minimum degree conditions for H-linked graphs

Research output: Contribution to journalArticlepeer-review

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 n ≥ 7.5 k, 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.

Original languageEnglish (US)
Pages (from-to)1542-1548
Number of pages7
JournalDiscrete Applied Mathematics
Volume156
Issue number9
DOIs
StatePublished - May 1 2008

Keywords

  • Degree conditions
  • Extremal graph problems
  • H-linked graphs

ASJC Scopus subject areas

  • Discrete Mathematics and Combinatorics
  • Applied Mathematics

Fingerprint

Dive into the research topics of 'Minimum degree conditions for H-linked graphs'. Together they form a unique fingerprint.

Cite this