2016/11/25 by Abdullah Makkeh, Makkeh, Abdullah, Mozhgan Pourmoradnasseri +3 · 1 citation
Computer Science · Engineering · #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Graph Labeling and Dimension Problems #Optimization and Packing Problems #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.1611.08431
openalex publication_date 2016/11/25 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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".