The Subtour
Elimination Problem (SEP) is the LP relaxation of the Symmetric Travelling
Salesman Problem. Let S^{n} represent the polytope
associated with the SEP on n nodes.

Below are the files that contain a
complete list of all the vertices of S^{n} ,6 £ n ≤ 12, which have
non-isomorphic weighted support graphs.
Note that for n £ 5, all the vertices of S^{n} represent TSP tours. The description of how these files were
generated for 6 £ n ≤ 10 can be found in

Benoit, G.,** Boyd, S.** (2008), __Finding the exact integrality gap for small
traveling salesman problems__ (journal version*), Mathematics of Operations
Research*, Volume 33, Number 4, 921-931.

and for n=11, 12 can be found in

**Boyd, S.**,
Elliott-Magwood, P. (2010), Structure
of the Extreme Points of the Subtour Elimination
Problem of the STSP, In: S. Iwata, editor, *Combinatorial Optimization and Discrete Algorithms*, *RIMS Kôkyûroku Bessatsu B23*, Kyoto University, Kyoto, Japan, 33-47.

Let the nodes of the complete graph K_{n} be labelled 1, 2, 3, ..., n. In these
files, each line of text represents a vertex x of S^{n},
where the values of x_{e} for all edges e of
the complete graph K_{n}_{ }are
listed in the edge order 1-2, 1-3, 1-4, ..., 1-n, 2-3, 2-4, 2-5, ..., 2-n, 3-4,
.... etc.. Note
that the files do not include the tour for

6 £ n ≤ 10, but do include it for
n=11, 12.

If you desire to use these lists for
your research you are welcome to do so, but it would be appreciated if you
could reference this work, and contact me at *sylvia@site.uottawa*.ca

· Vertices for n=6 nodes: vertices_6.txt

· Vertices for n=7 nodes: vertices_7.txt

· Vertices for n=8 nodes: vertices_8.txt

· Vertices for n=9 nodes: vertices_9.txt

· Vertices for n=10 nodes: vertices_10.txt

Drawings of the weighted support graphs for n = 10: 10nodeverticespics.ps

· Vertices for n=11 nodes: vertices_11.txt

· Vertices for n=12 nodes: vertices_12.txt