✦ LIBER ✦

A short proof of the Chen-Manalastas theorem

✍ Scribed by J.A. Bondy

Publisher: Elsevier Science
Year: 1995
Tongue: English
Weight: 232 KB
Volume: 146
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(94)00173-1

No coin nor oath required. For personal study only.

✦ Synopsis

Gallai and Milgram (1960)

proved that a digraph with stability number ct is spanned by ct disjoint directed paths. Chen and Manalastas Jr (1983) proved that a strong digraph with stability number at most two is spanned by at most two consistent directed circuits. We slightly simplify the proof of the Gallai-Milgram theorem, while at the same time refining its statement, and use this sharpened version to obtain a relatively short proof of the Chen-Manalastas theorem. We also give a counterexample to a generalization of the Gallai-Milgram theorem conjectured by Hartman (1988).

📜 SIMILAR VOLUMES

A short proof of kundu's k-factor theore

A short proof of kundu's k-factor theorem

✍ Yong-Chuan Chen 📂 Article 📅 1988 🏛 Elsevier Science 🌐 English ⚖ 301 KB

We give a very short proof of the following theorem on k-factorable degree sequences due to Kundu [5]: Tbearem 1. Let (dl,d2,-.-,d,,) and.(d,-k,,d,-k,,...,d,-k,) be two graphical sequences satisfying k s ki s k + 1, 1 bi s n, for some k PO. Then there exists a' graph G =: (V, E) which contains a sub

A short proof of Martindale's theorem on

A short proof of Martindale's theorem on GPIs

✍ Chen-Lian Chuang 📂 Article 📅 1992 🏛 Elsevier Science 🌐 English ⚖ 223 KB

A short proof of the 3d distance theorem

✍ Frank M. Liang 📂 Article 📅 1979 🏛 Elsevier Science 🌐 English ⚖ 202 KB

Proof, There are d arithmdztic sequence8 inserted (mod 1) into [O, I], In the following, we will refer to the 'Mart" and "flni~h" points of each of the sequences, These are, respectively, the points {q) and {(q -I)@ t cu,) for 1 G i G d. The idea of the proof is to associate each interval in [O, I]

Short proofs of classical theorems

✍ J. A. Bondy 📂 Article 📅 2003 🏛 John Wiley and Sons 🌐 English ⚖ 81 KB

## Abstract We give proofs of Ore's theorem on Hamilton circuits, Brooks' theorem on vertex coloring, and Vizing's theorem on edge coloring, as well as the Chvátal‐Lovász theorem on semi‐kernels, a theorem of Lu on spanning arborescences of tournaments, and a theorem of Gutin on diameters of orient

A short proof of Chvátal's Watchman Theo

A short proof of Chvátal's Watchman Theorem

✍ Steve Fisk 📂 Article 📅 1978 🏛 Elsevier Science 🌐 English ⚖ 45 KB

A very short proof of Dixon's theorem

✍ Shalosh B Ekhad 📂 Article 📅 1990 🏛 Elsevier Science 🌐 English ⚖ 56 KB