1. Notes on heavy cycles in weighted digraphs
- Author
-
Li, Binlong and Zhang, Shenggui
- Subjects
- *
PATHS & cycles in graph theory , *DIRECTED graphs , *GRAPH theory , *TOPOLOGICAL degree , *EXISTENCE theorems , *LOGICAL prediction , *MATHEMATICAL analysis - Abstract
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 in a weighted digraph is the sum of the weights of the arcs with as their tail, and the weight of a directed cycle in is the sum of the weights of the arcs of . In this note we prove that if every vertex of a weighted digraph with order has weighted outdegree at least 1, then there exists a directed cycle in with weight at least . This proves a conjecture of Bollobás and Scott up to a constant factor. [Copyright &y& Elsevier]
- Published
- 2012
- Full Text
- View/download PDF