A PROOF OF A CONJECTURE OF BONDY CONCERNING PATHS IN WEIGHTED DIGRAPHS

Authors
BOLLOBAS B SCOTT AD
Citation
B. Bollobas et Ad. Scott, A PROOF OF A CONJECTURE OF BONDY CONCERNING PATHS IN WEIGHTED DIGRAPHS, J COMB TH B, 66(2), 1996, pp. 283-292
Citations number
22
Categorie Soggetti
Mathematics, Pure",Mathematics
Journal title
JOURNAL OF COMBINATORIAL THEORY SERIES B
ISSN journal
00958956 → ACNP
Volume
66
Issue
2
Year of publication
1996
Pages
283 - 292
Database
ISI
SICI code
0095-8956(1996)66:2<283:APOACO>2.0.ZU;2-O
Abstract
Our aim in this note is to prove a conjecture of Bondy, extending a cl assical theorem of Dirac to edge-weighted digraphs: if every vertex ha s out-weight at least 1 then the digraph contains a path of weight at least 1. We also give several related conjectures and results concerni ng heavy cycles in edge-weighted digraphs. (C) 1996 Academic Press, In c.