✦ LIBER ✦

Arc reversal in nonhamiltonian circulant oriented graphs

✍ Scribed by Jozef Jirásek

Publisher: John Wiley and Sons
Year: 2005
Tongue: English
Weight: 108 KB
Volume: 49
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.20063

No coin nor oath required. For personal study only.

✦ Synopsis

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 counterexamples to Ádám's conjecture on arc reversal. One of them is a counterexample with the smallest known number of vertices. © 2005 Wiley Periodicals, Inc. J Graph Theory 49: 59–68, 2005

📜 SIMILAR VOLUMES

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