Linkedness of Cartesian products of complete graphs

Leif K. Jorgensen; Guillermo Pineda-Villavicencio; Julien Ugon

paper

Linkedness of Cartesian products of complete graphs

arXiv:2012.05576

Abstract

This paper is concerned with the linkedness of Cartesian products of complete graphs. A graph with at least $2 k$ vertices is {\it $k$ -linked} if, for every set of $2 k$ 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} \geq 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.

11 pages, 2 figures