𝔖 Bobbio Scriptorium
✦   LIBER   ✦

A Proof of a Conjecture of Bondy Concerning Paths in Weighted Digraphs

✍ Scribed by B. Bollobás; A.D. Scott

Publisher
Elsevier Science
Year
1996
Tongue
English
Weight
365 KB
Volume
66
Category
Article
ISSN
0095-8956

No coin nor oath required. For personal study only.

✦ Synopsis

Our aim in this note is to prove a conjecture of Bondy, extending a classical theorem of Dirac to edge-weighted digraphs: if every vertex has out-weight at least 1 then the digraph contains a path of weight at least 1. We also give several related conjectures and results concerning heavy cycles in edge-weighted digraphs.

📜 SIMILAR VOLUMES

Covering a Strong Digraph by α−1 Disjoin
Covering a Strong Digraph by α−1 Disjoint Paths: A Proof of Las Vergnas' Conjecture
✍ Stéphan Thomassé 📂 Article 📅 2001 🏛 Elsevier Science 🌐 English ⚖ 83 KB

The Gallai Milgram theorem states that every directed graph D is spanned by :(D) disjoint directed paths, where :(D) is the size of a largest stable set of D. When :(D)>1 and D is strongly connected, it has been conjectured by Las Vergnas that D is spanned by an arborescence with :(D)&1 leaves. The

Oriented Hamiltonian Paths in Tournament
Oriented Hamiltonian Paths in Tournaments: A Proof of Rosenfeld's Conjecture
✍ Frédéric Havet; Stéphan Thomassé 📂 Article 📅 2000 🏛 Elsevier Science 🌐 English ⚖ 284 KB

We prove that with three exceptions, every tournament of order n contains each oriented path of order n. The exceptions are the antidirected paths in the 3-cycle, in the regular tournament on 5 vertices, and in the Paley tournament on 7 vertices. ## 2000 Academic Press Tournaments are very rich st

A very short proof of a conjecture conce
A very short proof of a conjecture concerning set-to-set broadcasting
✍ Qiao Li; Zhongliang Zhang; Junming Xu 📂 Article 📅 1993 🏛 John Wiley and Sons 🌐 English ⚖ 96 KB

We present a very short proof of a conjecture of Richards and Liestman concerning set-to-set broadcasting. 0 1993 by John Wiley & Sons, Inc.

Proof of a conjecture on cycles in a bip
Proof of a conjecture on cycles in a bipartite graph
✍ Wang, Hong 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 244 KB 👁 2 views

It was conjectured in [Wang, to appear in The Australasian Journal of Combinatorics] that, for each integer k ≥ 2, there exists . This conjecture is also verified for k = 2, 3 in [Wang, to appear; Wang, manuscript]. In this article, we prove this conjecture to be true if n ≥ 3k, i.e., M (k) ≤ 3k. W

Solution of a conjecture of Volkmann on
Solution of a conjecture of Volkmann on longest paths through an arc in strongly connected in-tournaments
✍ Dirk Meierling 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 139 KB 👁 1 views

## Abstract An in‐tournament is an oriented graph such that the negative neighborhood of every vertex induces a tournament. Let __m__ = 4 or __m__ = 5 and let __D__ be a strongly connected in‐tournament of order ${{n}}\geq {{2}}{{m}}-{{2}}$ such that each arc belongs to a directed path of order at