On minimum degree implying that a graph is H-linked

Ronald J. Gould, Alexandr Kostochka, Yu Gexin

Research output: Contribution to journalArticlepeer-review

Abstract

Given a fixed multigraph H, possibly containing loops, 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 V i is the branch vertex representing h i (for all i). This generalizes the concept of k-linked graphs (as well as a number of other well-known path or cycle properties). In this paper we determine a sharp lower bound on δ(G) (which depends upon H) such that each graph G on at least 10(|V(H)| + |E(H)|) vertices satisfying this bound is H-linked.

Original languageEnglish (US)
Pages (from-to)829-840
Number of pages12
JournalSIAM Journal on Discrete Mathematics
Volume20
Issue number4
DOIs
StatePublished - 2007

Keywords

  • Connectivity
  • H-linked
  • Minimum degree
  • k-linked

ASJC Scopus subject areas

  • General Mathematics

Fingerprint

Dive into the research topics of 'On minimum degree implying that a graph is H-linked'. Together they form a unique fingerprint.

Cite this