Name
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. |
Year | DOI | Venue |
|---|---|---|
1997 | 10.1137/S0895480195283798 | SIAM J. Discrete Math. |
Keywords | Field | DocType |
density function,total number,salesman polytope,asymmetric traveling salesman polytope,log n,g. boccara,positive integer k,discrete math,lower bound,small value,degree n,adjacency,permutation group,traveling salesman | Integer,Discrete mathematics,Combinatorics,Vertex (geometry),Upper and lower bounds,Permutation group,Polytope,Omega,Degree (graph theory),Conjecture,Mathematics | Journal |
Volume | Issue | ISSN |
10 | 3 | 0895-4801 |
Citations | PageRank | References |
0 | 0.34 | 4 |
Authors | ||
1 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| A. Sarangarajan | 1 | 31 | 9.42 |