On the skeleton of the pyramidal tours polytope

Vladimir A. Bondarenko; Andrei V. Nikolaev

doi:10.1134/S1990478918010027

paper

On the skeleton of the pyramidal tours polytope

arXiv:1710.06286 · doi:10.1134/S1990478918010027

Abstract

We consider the skeleton of the pyramidal tours polytope. Hamiltonian tour is called pyramidal if the salesperson starts in city $1$ , then visits some cities in increasing order, reaches city $n$ and returns to city $1$ , visiting the remaining cities in decreasing order. The polytope $P Y R (n)$ is defined as the convex hull of characteristic vectors of all pyramidal tours in the complete graph $K_{n}$ . The skeleton of the polytope $P Y R (n)$ is the graph whose vertex set is the vertex set of $P Y R (n)$ and edge set is the set of geometric edges or one-dimensional faces of $P Y R (n)$ . We describe the necessary and sufficient condition for the adjacency of vertices of the polytope $P Y R (n)$ . On this basis we developed an algorithm to check the vertex adjacency with a linear complexity. We establish that the diameter of $P Y R (n)$ skeleton equals 2, and the asymptotically exact estimate of $P Y R (n)$ skeleton's clique number is $Θ (n^{2})$ . It is known that this value characterizes the time complexity in a broad class of algorithms based on linear comparisons.