Arc reversal in nonhamiltonian circulant oriented graphs | Zendy

Jirásek Jozef | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

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

This content is not available in your region!

Continue researching here.

Having issues? You can contact us here

Accelerating Research