This article is cited in
12 papers
On the skeleton of the polytope of pyramidal tours
V. A. Bondarenko,
A. V. Nikolaev Demidov Yaroslavl State University, 14 Sovetskaya St., 150003 Yaroslavl, Russia
Abstract:
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.
Keywords:
pyramidal tour, $1$-skeleton, necessary and sufficient condition of adjacency, clique number, graph diameter.
UDC:
519.16+
514.172.45 Received: 03.03.2017
DOI:
10.17377/daio.2018.25.570
Fulltext:
PDF file (349 kB)