A note on heavy cycles in weighted digraphs

Details A note on heavy cycles in weighted digraphs A note on heavy cycles in weighted digraphs

2011-09-21

arxiv.org/abs/1109.4676v3

Mathematics

Combinatorics

Scientific paper

A weighted digraph is a digraph such that every arc is assigned a nonnegative number, called the weight of the arc. The weighted outdegree of a vertex $v$ in a weighted digraph $D$ is the sum of the weights of the arcs with $v$ as their tail, and the weight of a directed cycle $C$ in $D$ is the sum of the weights of the arcs of $C$. In this note we prove that if every vertex of a weighted digraph $D$ with order $n$ has weighted outdegree at least 1, then there exists a directed cycle in $D$ with weight at least $1/\log_2 n$. This proves a conjecture of Bollob\'{a}s and Scott up to a constant factor.

Affiliated with

Also associated with

No associations

Rating

A note on heavy cycles in weighted digraphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with A note on heavy cycles in weighted digraphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A note on heavy cycles in weighted digraphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-261943