Search

Abstract: Bollobás and Scott proved that if the weighted outdegree of every vertex of an edge-weighted digraph is at least 1, then the digraph contains a (directed) path of weight at least 1. In this note we characterize the extremal weighted digraphs with no heavy paths. Our result extends a corresponding theorem of Bondy and Fan on weighted graphs. We also give examples to show that a result of Bondy and Fan on the existence of heavy paths connecting two given vertices in a 2-connected weighted graph does not extend to 2-connected weighted digraphs. [Copyright &y& Elsevier]

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]