Notes on heavy cycles in weighted digraphs

DOI10.1016/J.AML.2012.01.025MaRDI QIDQ712569zbMATH OpenOpenAlexFDO

Authors Binlong Li, Shenggui Zhang

Publication date 17 October 2012

Published in Applied Mathematics Letters (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1109.4676

zbMATH Keywords

heavy directed cycleweighted digraphweighted outdegree

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Signed and weighted graphs (05C22) Paths and cycles (05C38)

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/lo{g}_{2}n$. This proves a conjecture of Bollob'{a}s and Scott up to a constant factor.

Recommendations

• A proof of a conjecture of Bondy concerning paths in weighted digraphs
• Cycles in weighted graphs
• A new proof of a theorem on the existence of heavy cycles in weighted graphs
• Heavy cycles in weighted graphs

Cites work

• A proof of a conjecture of Bondy concerning paths in weighted digraphs
• Graph theory

Cited in

(2)

• A proof of a conjecture of Bondy concerning paths in weighted digraphs
• Long cycles, heavy cycles and cycle decompositions in digraphs

This page was built for publication: Notes on heavy cycles in weighted digraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q712569)