𝔖 Bobbio Scriptorium
✦   LIBER   ✦

A note on vertex pancyclic oriented graphs

✍ Scribed by Bang-Jensen, J�rgen; Guo, Yubao

Publisher
John Wiley and Sons
Year
1999
Tongue
English
Weight
185 KB
Volume
31
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

Let D be an oriented graph of order n ≥ 9, minimum degree at least n -2, such that, for the choice of distinct vertices x and y, . Graph Theory 18 (1994), 461-468) proved that D is pancyclic. In this note, we give a short proof, based on Song's result, that D is, in fact, vertex pancyclic. This also generalizes a result of Jackson (J. Graph Theory 5 (1981), 147-157) for the existence of a hamiltonian cycle in oriented graphs.

📜 SIMILAR VOLUMES

On packing 3-vertex paths in a graph
On packing 3-vertex paths in a graph
✍ Atsushi Kaneko; Alexander Kelmans; Tsuyoshi Nishimura 📂 Article 📅 2001 🏛 John Wiley and Sons 🌐 English ⚖ 276 KB 👁 1 views
A note on vertex orders for stability nu
A note on vertex orders for stability number
✍ Mahadev, N. V. R.; Reed, B. A. 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 115 KB 👁 1 views

We investigate vertex orders that can be used to obtain maximum stable sets by a simple greedy algorithm in polynomial time in some classes of graphs. We characterize a class of graphs for which the stability number can be obtained by a simple greedy algorithm. This class properly contains previousl

A note on the bottleneck graph partition
A note on the bottleneck graph partition problem
✍ Klinz, Bettina; Woeginger, Gerhard J. 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 47 KB 👁 2 views

The bottleneck graph partition problem consists of partitioning the vertices of an undirected edge-weighted graph into two equally sized sets such that the maximum edge weight in the cut separating the two sets becomes minimum. In this short note, we present an optimum algorithm for this problem wit

A note on mixed graphs and directed spli
A note on mixed graphs and directed splitting off
✍ Enni, Steffen 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 329 KB 👁 1 views

We give counterexamples to two conjectures of Bill Jackson in Some remarks on arc-connectivity, vertex splitting, and orientation in graphs and digraphs (Journal of Graph Theory 12(3):429-436, 1988) concerning orientations of mixed graphs and splitting off in digraphs, and prove the first conjecture