✦ LIBER ✦

Digraphs with the path-merging property

✍ Scribed by Jørgen Bang-Jensen

Publisher: John Wiley and Sons
Year: 1995
Tongue: English
Weight: 595 KB
Volume: 20
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.3190200214

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

In this paper we study those digraphs D for which every pair of internally disjoint (X, Y)‐paths P~1~, P~2~ can be merged into one (X, Y)‐path P* such that V(P~1~) ∪ V(P~2~), for every choice of vertices X, Y ϵ V(D). We call this property the path‐merging property and we call a graph path‐mergeable if it has the path‐merging property. We show that each such digraph has a directed hamiltonian cycle whenever it can possibly have one, i.e., it is strong and the underlying graph has no cutvertex. We show that path‐mergeable digraphs can be recognized in polynomial time and we give examples of large classes of such digraphs which are not contained in any previously studied class of digraphs. We also discuss which undirected graphs have path‐mergeable digraph orientations. © 1995, John Wiley & Sons, Inc.

📜 SIMILAR VOLUMES

On digraphs with the odd cycle property

✍ Rachel Manber; Jia-Yu Shao 📂 Article 📅 1986 🏛 John Wiley and Sons 🌐 English ⚖ 462 KB

We say that a digraph D has the odd cycle property if there exists an edge subset S such that every cycle of D has an odd number of edges from S. We give necessary and sufficient conditions for a digraph to have the odd cycle property. We also consider the analogous problem for graphs.

Digraphs with maximum number of paths an

Digraphs with maximum number of paths and cycles

✍ Yehoshua Perl 📂 Article 📅 1987 🏛 John Wiley and Sons 🌐 English ⚖ 482 KB

The Hamiltonian property of consecutive-

The Hamiltonian property of consecutive-d digraphs

✍ D.Z. Du; D.F. Hsu; F.K. Hwang 📂 Article 📅 1993 🏛 Elsevier Science 🌐 English ⚖ 306 KB

The even-path problem for graphs and dig

The even-path problem for graphs and digraphs

✍ Andrea S. Lapaugh; Christos H. Papadimitriou 📂 Article 📅 1984 🏛 John Wiley and Sons 🌐 English ⚖ 357 KB

The Hamiltonian property of generalized

The Hamiltonian property of generalized de Bruijn digraphs

✍ D.Z Du; D.F Hsu; F.K Hwang; X.M Zhang 📂 Article 📅 1991 🏛 Elsevier Science 🌐 English ⚖ 512 KB

The Cycle-Path Indicator Polynomial of a

The Cycle-Path Indicator Polynomial of a Digraph

✍ Ottavio M. D'Antona; Emanuele Munarini 📂 Article 📅 2000 🏛 Elsevier Science 🌐 English ⚖ 126 KB

A cycle-path cover of a digraph D is a spanning subgraph made of disjoint cycles and paths. In order to count such covers by types we introduce the cyclepath indicator polynomial of D. We show that this polynomial can be obtained by a deletion-contraction recurrence relation. Then we study some spec