On the skeleton of the polytope of pyramidal tours

V. A. Bondarenko ; A. V. Nikolaev

Diskretnyj analiz i issledovanie operacij, Tome 25 (2018) no. 1, pp. 5-24

Résumé

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

Détail

Mots-clés : pyramidal tour
Keywords: $1$-skeleton, necessary and sufficient condition of adjacency, clique number, graph diameter.