✦ LIBER ✦

On complementary cycles in locally semicomplete digraphs

✍ Scribed by Yubao Guo; Lutz Volkmann

Publisher: Elsevier Science
Year: 1994
Tongue: English
Weight: 440 KB
Volume: 135
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(93)e0099-p

No coin nor oath required. For personal study only.

✦ Synopsis

In this paper we show that a 2-connected locally semicomplete digraph of order at least 8 is not cycle complementary if and only if it is 2-diregular and has odd order. This result yields immediately two conjectures of Bang-Jensen.

📜 SIMILAR VOLUMES

Kings in locally semicomplete digraphs

✍ Ruixia Wang; Aimin Yang; Shiying Wang 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 94 KB

## Abstract A __k__‐king in a digraph __D__ is a vertex which can reach every other vertex by a directed path of length at most __k__. We consider __k__‐kings in locally semicomplete digraphs and mainly prove that all strong locally semicomplete digraphs which are not round decomposable contain a 2

One-diregular subgraphs in semicomplete

One-diregular subgraphs in semicomplete multipartite digraphs

✍ Yeo, Anders 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 154 KB

The problem of finding necessary and sufficient conditions for a semicomplete multipartite digraph (SMD) to be Hamiltonian, seems to be both very interesting and difficult. Bang-Jensen, Gutin and Huang (Discrete Math to appear) proved a sufficient condition for a SMD to be Hamiltonian. A strengtheni

A polynomial algorithm for the Hamiltoni

A polynomial algorithm for the Hamiltonian cycle problem in semicomplete multipartite digraphs

✍ Bang-Jensen, J�rgen; Gutin, Gregory; Yeo, Anders 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 382 KB 👁 2 views

We describe a polynomial algorithm for the Hamiltonian cycle problem for semicomplete multipartite digraphs. The existence of such an algorithm was conjectured in G.

On cycles and paths in digraphs

✍ M.C. Heydemann 📂 Article 📅 1980 🏛 Elsevier Science 🌐 English ⚖ 273 KB

The purpose of this communication is to announce some slrfficient conditions on degrees and number of arcs to insure the existence of cycles and paths in directed graphs. We show that these results are the best possible. The proofs of the theorems can be found in [4].

A Polynomial Time Algorithm for Finding

A Polynomial Time Algorithm for Finding a Cycle Covering a Given Set of Vertices in a Semicomplete Multipartite Digraph

✍ Anders Yeo 📂 Article 📅 1999 🏛 Elsevier Science 🌐 English ⚖ 181 KB

On the existence of a specified cycle in

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

✍ Abdelhamid Benhocine 📂 Article 📅 1984 🏛 John Wiley and Sons 🌐 English ⚖ 326 KB 👁 1 views

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