✦ LIBER ✦

Every finite strongly connected digraph of stability 2 has a Hamiltonian path

✍ Scribed by C.C. Chen; P. Manalastas Jr.

Publisher: Elsevier Science
Year: 1983
Tongue: English
Weight: 333 KB
Volume: 44
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(83)90188-7

No coin nor oath required. For personal study only.

✦ Synopsis

Two circuits C~ and C 2 in a digraph are called consistent circuits if and only if their intersection is either empty, a singleton or a subpath of both C~ and C 2. It is proved that Every finite strongly connected digraph of G of stability at most 2 is spanned by two consistent circuits. As a consequence, every finite strongly connected digraph of stability two has a Hamiltonian path.