Title: A Lower Bound for Adjacencies on the Traveling Salesman Polytope
Abstract: We study adjacency of vertices on Tn, the asymmetric traveling salesman polytope of degree n. Applying a result of G. Boccara [Discrete Math., 29 (1980), pp. 105--134] to permutation groups, we show that Tn has $\Omega((n-1)(n-2)!\,^2 \log n)$ edges, implying that the degree of a vertex of Tn is $\Omega((n-2)! \log n)$. We conjecture the degree to be $\Omega((n-2)! (\log n)^k)$ for any positive integer k. We compute the density function $\delta_n$ given by the fraction of the total number of vertices adjacent to a given vertex for small values of n, and conjecture that it decreases with n.
Publication Year: 1997
Publication Date: 1997-08-01
Language: en
Type: article
Indexed In: ['crossref']
Access and Citation
Cited By Count: 4
AI Researcher Chatbot
Get quick answers to your questions about the article from our AI researcher chatbot