𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Interchange graphs and the Hamiltonian cycle polytope

✍ Scribed by Gerard Sierksma

Publisher
Elsevier Science
Year
1998
Tongue
English
Weight
464 KB
Volume
81
Category
Article
ISSN
0166-218X

No coin nor oath required. For personal study only.

✦ Synopsis

This paper answers the (non)adjacency question for the whole spectrum of Hamiltonian cycles on the Hamiltonian cycle polytope (HC-polytope), also called the symmetric traveling salesman polytope, namely from Hamiltonian cycles that differ in only two edges through Hamiltonian cycles that are edge disjoint. The HC-polytope is the convex hull of the characteristic vectors

πŸ“œ SIMILAR VOLUMES

On the cycle polytope of a directed grap
On the cycle polytope of a directed graph
✍ Egon Balas; Maarten Oosten πŸ“‚ Article πŸ“… 2000 πŸ› John Wiley and Sons 🌐 English βš– 185 KB πŸ‘ 2 views
Disjoint Cycles in Eulerian Digraphs and
Disjoint Cycles in Eulerian Digraphs and the Diameter of Interchange Graphs
✍ Richard A. Brualdi; Jian Shen πŸ“‚ Article πŸ“… 2002 πŸ› Elsevier Science 🌐 English βš– 87 KB

denote the set of all m Γ— n {0, 1}-matrices with row sum vector R and column sum vector S. Suppose A(R, S) ] ". The interchange graph G(R, S) of A(R, S) was defined by Brualdi in 1980. It is the graph with all matrices in A(R, S) as its vertices and two matrices are adjacent provided they differ by

Cyclic Hamiltonian cycle systems of the
Cyclic Hamiltonian cycle systems of the complete graph
✍ Marco Buratti; Alberto Del Fra πŸ“‚ Article πŸ“… 2004 πŸ› Elsevier Science 🌐 English βš– 251 KB

We prove that there exists a cyclic Hamiltonian k-cycle system of the complete graph if and only if k is odd but k = 15 and p with p prime and ΒΏ 1. As a consequence we have the existence of a cyclic k-cycle system of the complete graph on km vertices for any pair (k; m) of odd integers with k as abo