๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

Heavy cycles and spanning trees with few leaves in weighted graphs

โœ Scribed by Binlong Li; Shenggui Zhang

Publisher
Elsevier Science
Year
2011
Tongue
English
Weight
205 KB
Volume
24
Category
Article
ISSN
0893-9659

No coin nor oath required. For personal study only.

โœฆ Synopsis

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.

๐Ÿ“œ SIMILAR VOLUMES

Heavy cycles passing through some specif
Heavy cycles passing through some specified vertices in weighted graphs
โœ Jun Fujisawa; Kiyoshi Yoshimoto; Shenggui Zhang ๐Ÿ“‚ Article ๐Ÿ“… 2005 ๐Ÿ› John Wiley and Sons ๐ŸŒ English โš– 111 KB

## Abstract A weighted graph is one in which every edge __e__ is assigned a nonnegative number, called the weight of __e__. The sum of the weights of the edges incident with a vertex ฯ… is called the weighted degree of ฯ…. The weight of a cycle is defined as the sum of the weights of its edges. In th

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.