𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Paths and cycles in extended and decomposable digraphs

✍ Scribed by Jørgen Bang-Jensen; Gregory Gutin

Publisher
Elsevier Science
Year
1997
Tongue
English
Weight
835 KB
Volume
164
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

✦ Synopsis

We consider digraphs --called extended locally semicomplete digraphs, or extended LSD's, for short --that can be obtained from locally semicomplete digraphs by substituting independent sets for vertices. We characterize Hamiltonian extended LSD's as well as extended LSD's containing Hamiltonian paths. These results as well as some additional ones imply polynomial algorithms for finding a longest path and a longest cycle in an extended LSD. Our characterization of Hamiltonian extended LSD's provides a partial solution to a problem posed by H/iggkvist (I 993). Combining results from this paper with some general results derived for the so-called totally ~-decomposable digraphs in Bang-Jensen and Gutin (1996) we prove that the longest path problem is polynomially solvable for totally ~0-decomposable digraphs --a fairly wide family of digraphs which is a common generalization of acyclic digraphs, semicomplete multipartite digraphs, extended LSD's and quasi-transitive digraphs. Similar results are obtained for the longest cycle problem and other problems on cycles in subfamilies of totally q~0-decomposable digraphs. These polynomial algorithms are a natural and fairly deep generalization of algorithms obtained for quasi-transitive digraphs in Bang-Jensen and Gutin (1996) in order to solve a problem posed by N. Alon.

📜 SIMILAR VOLUMES

On cycles and paths in digraphs
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].

Tools for studying paths and cycles in d
Tools for studying paths and cycles in digraphs
✍ Delorme, C.; Ordaz, O.; Quiroz, D. 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 251 KB

The main goal of this work was to describe the basic elements constituting a specialized knowledge base in the field of paths and circuits in digraphs. This knowledge base contains commented on examples with textual and graphical descriptions, invariants, relations among invariants, and theorems. It

Cycle extendability in graphs and digrap
Cycle extendability in graphs and digraphs
✍ LeRoy B. Beasley; David E. Brown 📂 Article 📅 2011 🏛 Elsevier Science 🌐 English ⚖ 201 KB

In 1990, Hendry conjectured that all chordal Hamiltonian graphs are cycle extendable, that is, the vertices of each non-Hamiltonian cycle are contained in a cycle of length one greater. Let A be a symmetric (0,1)-matrix with zero main diagonal such that A is the adjacency matrix of a chordal Hamilto

Vertex heaviest paths and cycles in quas
Vertex heaviest paths and cycles in quasi-transitive digraphs
✍ Jørgen Bang-Jensen; Gregory Gutin 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 381 KB

A digraph D is called a quasi-transitive digraph (QTD) if for any triple x,y,z of distinct vertices of D such that (x,y) and (y,z) are arcs of D there is at least one at': from x to z or from z to x. Solving a conjecture by Bangdensen and Huang (1995), Gutin (1995) described polynomial algorithms fo