On the Graph of the Pedigree Polytope

arXiv1611.08431MaRDI QIDQ6280135FDOQ6280135

Authors: Abdullah Makkeh, Mozhgan Pourmoradnasseri, Dirk Oliver Theis 

Publication date: 25 November 2016

Abstract: Pedigree polytopes are extensions of the classical Symmetric Traveling Salesman Problem polytopes whose graphs (1-skeletons) contain the TSP polytope graphs as spanning subgraphs. While deciding adjacency of vertices in TSP polytopes is coNP-complete, Arthanari has given a combinatorial (polynomially decidable) characterization of adjacency in Pedigree polytopes. Based on this characterization, we study the graphs of Pedigree polytopes asymptotically, for large numbers of cities. Unlike TSP polytope graphs, which are vertex transitive, Pedigree graphs are not even regular. Using an "adjacency game" to handle Arthanari's intricate inductive characterization of adjacency, we prove that the minimum degree is asymptotically equal to the number of vertices, i.e., the graph is "asymptotically almost complete".

This page was built for publication: On the Graph of the Pedigree Polytope

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6280135)