Linkedness of Cartesian products of complete graphs

Abstract

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 × K^d₂+1 of complete graphs K^d₁+1 and K^d₂+1 is ⌊(d₁ + d₂)/2⌋-linked for d₁, d₂ ≥ 2, and this is best possible.

This result is connected to graphs of simple polytopes. The Cartesian product K^d₁+1 × K^d₂+1 is the graph of the Cartesian product T(d₁) × T(d₂) of a d₁-dimensional simplex T(d₁) and a d₂-dimensional simplex T(d₂). And the polytope T(d₁) × T(d₂) is a simple polytope, a (d₁ + d₂)-dimensional polytope in which every vertex is incident to exactly d₁ + d₂ edges.

While not every d-polytope is ⌊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.