On the existence of a specified cycle in digraphs with constraints on degrees

✍ Scribed by Abdelhamid Benhocine

• Publisher: John Wiley and Sons
• Year: 1984
• Tongue: English
• Weight: 326 KB
• Volume: 8
• Category: Article
• ISSN: 0364-9024
• DOI: 10.1002/jgt.3190080111

✦ Synopsis

We prove that Woodall's and GhouileHouri's conditions on degrees which ensure that a digraph is Hamiltonian, also ensure that it contains the analog of a directed Hamiltonian cycle but with one edge pointing the wrong way; that is, it contains two vertices that are connected in the same direction by both an edge and a Hamiltonian path.

Throughout this paper, D will denote a finite digraph without loops or multiple edges, with vertex-set V(D) and edge-set E(D). If (x. y ) is an edge of D , it is symmetric if ( y , x) E E(D) and antisymmetric otherwise.

We define e(x * y) to be 1 if (x, y ) E E(D) and 0 otherwise, and e(x, y) = e(x -+ y ) + e(y + x). Similarly, if A and B are subsets of V(D), then e(A + B) denotes the number of edges leaving A and entering B, and e ( A , B) = e(A + B) + e(B 4 A). For n 3 3 and 2 d p G n, D(n, P ) = [XI. ..., X p ; xI, y l , ..., yn-p, xp] denotes the digraph on n distinct vertices x I , ..., x,, y l , ..., Y , , -~, composed by a directed path (xl, ..., x,) and a directed path ( x I , y I , ..

., yn-pr xp).

Many sufficient conditions ensuring a directed Hamiltonian cycle have been found (see the survey by Bermond and Thomassen [3]). Analogous conditions can be extended to D(n, p ) and even for cycles of length n with any orientation. For example, in [2] we proved that D(n, p ) exists in every tournament of order n (except for four exceptional tournaments); independently, Thomason [lo] proved the result that a tournament of order n contains every orientation of a Hamiltonian cycle for n sufficiently