Premium
Hamiltonicity and reversing arcs in digraphs
Author(s) -
Klostermeyer William F.,
S˘oltés L˘ubomír
Publication year - 1998
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/(sici)1097-0118(199805)28:1<13::aid-jgt2>3.0.co;2-i
Subject(s) - combinatorics , reversing , mathematics , digraph , graph , discrete mathematics , multipartite , complement graph , graph power , line graph , materials science , composite material , physics , quantum mechanics , quantum entanglement , quantum
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. © 1998 John Wiley & Sons, Inc. J Graph Theory 28: 13–30, 1998