𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Spanning trees with many leaves

✍ Scribed by Guoli Ding; Thor Johnson; Paul Seymour

Publisher
John Wiley and Sons
Year
2001
Tongue
English
Weight
95 KB
Volume
37
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

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

πŸ“œ SIMILAR VOLUMES

Spanning trees with leaf distance at lea
Spanning trees with leaf distance at least four
✍ Atsushi Kaneko; M. Kano; Kazuhiro Suzuki πŸ“‚ Article πŸ“… 2007 πŸ› John Wiley and Sons 🌐 English βš– 175 KB

## Abstract For a graph __G__, we denote by __i__(__G__) the number of isolated vertices of __G__. We prove that for a connected graph __G__ of order at least five, if __i__(__G__–__S__) < |__S__| for all βˆ…οΈ β‰  __S__ βŠ† __V__(__G__), then __G__ has a spanning tree __T__ such that the distance in __T_

A note on graphs with diameter-preservin
A note on graphs with diameter-preserving spanning trees
✍ Fred Buckley; Martin Lewinter πŸ“‚ Article πŸ“… 1988 πŸ› John Wiley and Sons 🌐 English βš– 182 KB πŸ‘ 1 views

The distance between a pair of vertices u, u in a graph G is the length of a shortest path joining u and u. The diameter diam(G) of G is the maximum distance between all pairs of vertices in G. A spanning tree Tof G is diameter preserving if diam(T) = diam(G). In this note, we characterize graphs th

On graphs with the maximum number of spa
On graphs with the maximum number of spanning trees
✍ Alexander K. Kelmans πŸ“‚ Article πŸ“… 1996 πŸ› John Wiley and Sons 🌐 English βš– 814 KB

Let 3:; denote the set of simple graphs with n vertices and m edges, t ( G ) the number of spanning trees of a graph G , and F 2 H if t(K,\E(F))?t(K,\E(H)) for every s? max{u(F), u ( H ) } . We give a complete characterization of >-maximal (maximum) graphs in 3:; subject to m 5 n . This result conta

Noncooperative cost spanning tree games
Noncooperative cost spanning tree games with budget restrictions
✍ Gustavo BergantiΓ±os; Leticia Lorenzo πŸ“‚ Article πŸ“… 2008 πŸ› John Wiley and Sons 🌐 English βš– 185 KB

## Abstract We extend the noncooperative game associated with the cost spanning tree problem introduced by BergantiΓ±os and Lorenzo (Math Method Oper Res 59(2004), 393–403) to situations where agents have budget restrictions. We study the Nash equilibria, subgame perfect Nash equilibria, and strong