𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Diameter-Preserving Spanning Trees in Sparse Weighted Graphs

✍ Scribed by Yue Liu; Jing Huang

Publisher
Springer Japan
Year
2009
Tongue
English
Weight
122 KB
Volume
25
Category
Article
ISSN
0911-0119

No coin nor oath required. For personal study only.

πŸ“œ SIMILAR VOLUMES

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

Diameter of random spanning trees in a g
Diameter of random spanning trees in a given graph
✍ Fan Chung; Paul Horn; L. Lu πŸ“‚ Article πŸ“… 2011 πŸ› John Wiley and Sons 🌐 English βš– 144 KB πŸ‘ 1 views

## Abstract Motivated by the observation that the sparse tree‐like subgraphs in a small world graph have large diameter, we analyze random spanning trees in a given host graph. We show that the diameter of a random spanning tree of a given host graph __G__ is between and with high probability., w

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.

Trees in sparse random graphs
Trees in sparse random graphs
✍ W.Fernandez de la Vega πŸ“‚ Article πŸ“… 1988 πŸ› Elsevier Science 🌐 English βš– 471 KB