Premium
Arc reversal in nonhamiltonian circulant oriented graphs
Author(s) -
Jirásek Jozef
Publication year - 2005
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.20063
Subject(s) - counterexample , mathematics , combinatorics , conjecture , circulant matrix , arc (geometry) , discrete mathematics , hamiltonian (control theory) , circulant graph , hamiltonian path , graph , line graph , geometry , mathematical optimization , voltage graph
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