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^{ d_{ 1}+1}\times K^{ d_{ 2}+1}$ of complete graphs $K^{ d_{ 1}+1}$ and $K^{ d_{ 2}+1}$ is $\floor{ (d_{ 1}+d_{ 2})/2}$-linked for $d_{ 1},d_{ 2}\ge 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^{ d_{ 1}+1}\times K^{ d_{ 2}+1}$ is the graph of the Cartesian product $T(d_{ 1})\times 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})\times T(d_{ 2})$ is a { \it 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 $\floor{ d/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.

Categories: math.CO

Linkedness of Cartesian products of complete graphs