Linkedness of Cartesian products of complete graphs - Jorgensen, Leif K. (Ars mathematica contemporanea, 2022)
This paper is concerned with the linkedness of Cartesian products of complete graphs. A graph with at least ?$2k$? vertices is ?$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^{d_1+1} × K^{d_2+1}$? of complete graphs ?$K^{d_1+1}$? and ?$K^{d_2+1}$? is ?$\lfloor (d_1 + d_2)/2 \rfloor $?-linked for ?$d_1, d_2 ≥ 2$?, and this is best possible. This result is connected to graphs of simple polytopes. The Cartesian product ?$K^{d_1+1} × K^{d_2+1}$? is the graph of the Cartesian product ?$T(d_1) × T(d_2)$? of a ?$d_1$?-dimensional simplex ?$T(d_1)$? and a ?$d_2$?-dimensional simplex ?$T(d_2)$?. And the polytope ?$T(d_1) × T(d_2)$? is a simple polytope, a ?$(d_1 + d_2)$?-dimensional polytope in which every vertex is incident to exactly ?$d_1 + d_2$? edges. While not every ?$d$?-polytope is ?$\lfloor d/2 \rfloor $?-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.
Keywords: Cartesian product; ciklični politop; connectivity; cyclic polytope; dual polytope; dualni politop; kartezični produkt; k-linked; k-vezan; linkedness; povezljivost; vezanost