Trees through specified vertices

Research output: Contribution to journalArticle

1 Citation (Scopus)

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

Fingerprint

Hamiltonians
Hamiltonian circuit
Paul Adrien Maurice Dirac
Connected graph
Theorem

Keywords

  • Subtrees through specified vertices

Cite this

Cutler, Jonathan. / Trees through specified vertices. In: Discrete Mathematics. 2009 ; Vol. 309, No. 9. pp. 2749-2754.
@article{83c6b9ebdbd8494f92d3a24017552666,
title = "Trees through specified vertices",
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.",
keywords = "Subtrees through specified vertices",
author = "Jonathan Cutler",
year = "2009",
month = "5",
day = "6",
doi = "10.1016/j.disc.2008.06.032",
language = "English",
volume = "309",
pages = "2749--2754",
journal = "Discrete Mathematics",
issn = "0012-365X",
publisher = "Elsevier",
number = "9",

}

Trees through specified vertices. / Cutler, Jonathan.

In: Discrete Mathematics, Vol. 309, No. 9, 06.05.2009, p. 2749-2754.

Research output: Contribution to journalArticle

TY - JOUR

T1 - Trees through specified vertices

AU - Cutler, Jonathan

PY - 2009/5/6

Y1 - 2009/5/6

N2 - 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.

AB - 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.

KW - Subtrees through specified vertices

UR - http://www.scopus.com/inward/record.url?scp=67349272020&partnerID=8YFLogxK

U2 - 10.1016/j.disc.2008.06.032

DO - 10.1016/j.disc.2008.06.032

M3 - Article

AN - SCOPUS:67349272020

VL - 309

SP - 2749

EP - 2754

JO - Discrete Mathematics

JF - Discrete Mathematics

SN - 0012-365X

IS - 9

ER -