A note on heavy cycles in weighted digraphs

2011/09/21 by Binlong Li, Li, Binlong, Shenggui Zhang +1
Mathematics · #05C20 #05C38 #Combinatorics (math.CO) #FOS: Mathematics #math.CO #msc:05C20 #msc:05C38

paper · pdf · doi:10.48550/arxiv.1109.4676

arxiv created 2012/02/03 · arxiv updated 2012/02/06

Abstract

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₂ n. This proves a conjecture of Bollobás and Scott up to a constant factor.

Related

• Long Cycles, Heavy Cycles and Cycle Decompositions in Digraphs
• Bounds on Maximum Weight Directed Cut
• The Arc-Weighted Version of the Second Neighborhood Conjecture
• Cycles of weight divisible by k
• A note on directed 4-cycles in digraphs