Trees through specified vertices

Research output: Contribution to journalArticle

1 Scopus citations

Abstract

We prove a conjecture of Horak that can be thought of as an extension of classical results including Dirac's theorem on the existence of Hamiltonian cycles. Namely, we prove for 1 ≤ k ≤ n - 2 if G is a connected graph with A ⊂ V (G) such that dG (v) ≥ k for all v ∈ A, then there exists a subtree T of G such that V (T) ⊃ A and dT (v) ≤ ⌈ frac(n - 1, k) ⌉ for all v ∈ A.

Original languageEnglish
Pages (from-to)2749-2754
Number of pages6
JournalDiscrete Mathematics
Volume309
Issue number9
DOIs
StatePublished - 6 May 2009

Keywords

  • Subtrees through specified vertices

Fingerprint Dive into the research topics of 'Trees through specified vertices'. Together they form a unique fingerprint.

  • Cite this