✦ LIBER ✦

Spanning Trees with Few Leaves

✍ Scribed by Masao Tsugaki; Tomoki Yamashita

Publisher: Springer Japan
Year: 2007
Tongue: English
Weight: 272 KB
Volume: 23
Category: Article
ISSN: 0911-0119
DOI: 10.1007/s00373-007-0751-y

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

Heavy cycles and spanning trees with few

Heavy cycles and spanning trees with few leaves in weighted graphs

✍ Binlong Li; Shenggui Zhang 📂 Article 📅 2011 🏛 Elsevier Science 🌐 English ⚖ 205 KB

Let G be a 2-connected weighted graph and k ≥ 2 an integer. In this note we prove that if the sum of the weighted degrees of every k + 1 pairwise nonadjacent vertices is at least m, then G contains either a cycle of weight at least 2m/(k + 1) or a spanning tree with no more than k leaves.

Spanning trees with many leaves

✍ Guoli Ding; Thor Johnson; Paul Seymour 📂 Article 📅 2001 🏛 John Wiley and Sons 🌐 English ⚖ 95 KB

## Abstract We show that if __G__ is a simple connected graph with and $|V(G)| \,\neq\,t+2$, then __G__ has a spanning tree with > __t__ leaves, and this is best possible. © 2001 John Wiley & Sons, Inc. J Graph Theory 37: 189–197, 2001

Spanning trees with many leaves

✍ D. V. Karpov 📂 Article 📅 2011 🏛 Springer US 🌐 English ⚖ 211 KB

Spanning Trees Crossing Few Barriers

✍ Tetsuo Asano; Mark de Berg; Otfried Cheong; Leonidas J. Guibas; Jack Snoeyink; H 📂 Article 📅 2003 🏛 Springer 🌐 English ⚖ 232 KB

On a Spanning Tree with Specified Leaves

✍ Yoshimi Egawa; Haruhide Matsuda; Tomoki Yamashita; Kiyoshi Yoshimoto 📂 Article 📅 2008 🏛 Springer Japan 🌐 English ⚖ 88 KB

Intersection representation of digraphs

Intersection representation of digraphs in trees with few leaves

✍ Lin, In-Jen; Sen, Malay K.; West, Douglas B. 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 285 KB 👁 2 views

The leafage of a digraph is the minimum number of leaves in a host tree in which it has a subtree intersection representation. We discuss bounds on the leafage in terms of other parameters (including Ferrers dimension), obtaining a string of sharp inequalities.