𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Hamiltonicity and reversing arcs in digraphs

✍ Scribed by Klostermeyer, William F.; S?olt�s, L?ubom�r

Publisher
John Wiley and Sons
Year
1998
Tongue
English
Weight
282 KB
Volume
28
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

In this paper we introduce a new hamiltonian-like property of graphs. A graph G is said to be cyclable if for each orientation D of G there is a set S of vertices such that reversing all the arcs of D with one end in S results in a hamiltonian digraph. We characterize cyclable complete multipartite graphs and prove that the fourth power of any connected graph G with at least five vertices is cyclable. If, moreover, G is two-connected then its cube is cyclable. These results are shown to be best possible in a sense.

📜 SIMILAR VOLUMES

Oriented hamilton cycles in digraphs
Oriented hamilton cycles in digraphs
✍ Roland Häggkvist; Andrew Thomason 📂 Article 📅 1995 🏛 John Wiley and Sons 🌐 English ⚖ 473 KB

## Abstract We show that a directed graph of order __n__ will contain __n__‐cycles of every orientation, provided each vertex has indegree and outdegree at least (1/2 + __n__^‐1/6^)__n__ and __n__ is sufficiently large. © 1995 John Wiley & Sons, Inc.

On Hamiltonicity of Vertex-Transitive Gr
On Hamiltonicity of Vertex-Transitive Graphs and Digraphs of Orderp4
✍ Yu Qing Chen 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 352 KB

The main result of this paper is that vertex-transitive graphs and digraphs of order p 4 are Hamiltonian, where p is a prime number. 1998 Academic Press 1. INTRODUCTION Witte [7] proved that Cayley digraphs of finite p-groups are Hamiltonian. In [2], Marus$ ic$ showed that all vertex-transitive digr

Local Strongly Arc-Connectivity in Regul
Local Strongly Arc-Connectivity in Regular Bipartite Digraphs
✍ J.M. Xu 📂 Article 📅 1993 🏛 Elsevier Science 🌐 English ⚖ 99 KB

We show that for any vertex \(x\) of a \(d\)-regular bipartite digraph there are a vertex \(y\), in the other class of the bipartition, and \(d(x, y)\)-paths and \(d(y, x)\)-paths such that all \(2 d\) of them are pairwise arc-disjoint. This result generalizes a theorem of Hamidoune and Las Vergnas

Some remarks on Arc-connectivity, vertex
Some remarks on Arc-connectivity, vertex splitting, and orientation in graphs and digraphs
✍ Bill Jackson 📂 Article 📅 1988 🏛 John Wiley and Sons 🌐 English ⚖ 309 KB

We apply proof techniques developed by L. Lovasz and A. Frank to obtain several results on the arc-connectivity of graphs and digraphs. The first results concern the operation of splitting two arcs from a vertex of an Eulerian graph or digraph in such a way as to preserve local connectivity conditio

Arc reversal in nonhamiltonian circulant
Arc reversal in nonhamiltonian circulant oriented graphs
✍ Jozef Jirásek 📂 Article 📅 2005 🏛 John Wiley and Sons 🌐 English ⚖ 108 KB

## Abstract Locke and Witte described infinite families of nonhamiltonian circulant oriented graphs. We show that for infinitely many of them the reversal of any arc produces a hamiltonian cycle. This solves an open problem stated by Thomassen in 1987. We also use these graphs to construct countere