### 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 d_{G} (v) ≥ k for all v ∈ A, then there exists a subtree T of G such that V (T) ⊃ A and d_{T} (v) ≤ ⌈ frac(n - 1, k) ⌉ for all v ∈ A.

Original language | English |
---|---|

Pages (from-to) | 2749-2754 |

Number of pages | 6 |

Journal | Discrete Mathematics |

Volume | 309 |

Issue number | 9 |

DOIs | |

State | Published - 6 May 2009 |

### Fingerprint

### Keywords

- Subtrees through specified vertices

### Cite this

*Discrete Mathematics*,

*309*(9), 2749-2754. https://doi.org/10.1016/j.disc.2008.06.032

}

*Discrete Mathematics*, vol. 309, no. 9, pp. 2749-2754. https://doi.org/10.1016/j.disc.2008.06.032

**Trees through specified vertices.** / Cutler, Jonathan.

Research output: Contribution to journal › Article

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 -