On the skeleton of the pyramidal tours polytope

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 $PYR(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 $PYR(n)$ is the graph whose vertex set is the vertex set of $PYR(n)$ and edge set is the set of geometric edges or one-dimensional faces of $PYR(n)$. We describe the necessary and sufficient condition for the adjacency of vertices of the polytope $PYR(n)$. On this basis we developed an algorithm to check the vertex adjacency with a linear complexity. We establish that the diameter of $PYR(n)$ skeleton equals 2, and the asymptotically exact estimate of $PYR(n)$ skeleton's clique number is $\Theta (n^2)$. It is known that this value characterizes the time complexity in a broad class of algorithms based on linear comparisons.

References in corpus (1)

• 1-skeletons of the spanning tree problems with additional constraints

Cited by in corpus (8)

• On vertex adjacencies in the polytope of pyramidal tours with step-backs
• Simulated annealing approach to verify vertex adjacencies in the traveling salesperson polytope
• An iterative ILP approach for constructing a Hamiltonian decomposition of a regular multigraph
• On 1-skeleton of the cut polytopes
• Hamiltonian decomposition and verifying vertex adjacency in 1-skeleton of the traveling salesperson polytope by variable neighborhood search
• Backtracking algorithms for constructing the Hamiltonian decomposition of a 4-regular multigraph
• On cone partitions for the min-cut and max-cut problems with non-negative edges
• Finding a second Hamiltonian decomposition of a 4-regular multigraph by integer linear programming