2020/12/10 by Leif K. Jørgensen, Guillermo Pineda‐Villavicencio, Jorgensen, Leif K. +3
Computer Science · Engineering · #Advanced Graph Theory Research #Combinatorics (math.CO) #Computational Geometry and Mesh Generation #FOS: Mathematics #Primary 05C40 #Secondary 52B05 #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.2012.05576
openalex publication_date 2020/12/10 · openalex created_date 2020/12/21 · openalex updated_date 2026/07/28
This paper is concerned with the linkedness of Cartesian products of complete graphs. A graph with at least 2k vertices is \it k-linked if, for every set of 2k distinct vertices organised in arbitrary k pairs of vertices, there are k vertex-disjoint paths joining the vertices in the pairs. We show that the Cartesian product K^d1+1× K^d2+1 of complete graphs K^d1+1 and K^d2+1 is \floor(d1+d2)/2-linked for d1,d2≥ 2, and this is best possible. %A polytope is said to be \it k-linked if its graph is k-linked. This result is connected to graphs of simple polytopes. The Cartesian product K^d1+1× K^d2+1 is the graph of the Cartesian product T(d1)× T(d2) of a d1-dimensional simplex T(d1) and a d2-dimensional simplex T(d2). And the polytope T(d1)× T(d2) is a \it simple polytope, a (d1+d2)-dimensional polytope in which every vertex is incident to exactly d1+d2 edges. While not every d-polytope is \floord/2-linked, it may be conjectured that every simple d-polytope is. Our result implies the veracity of the revised conjecture for Cartesian products of two simplices.