Linkedness of Cartesian products of complete graphs

Leif K. Jørgensen, Guillermo Pineda-Villavicencio, Julien Ugon


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 Kd1+1 × Kd2+1 of complete graphs Kd1+1 and Kd2+1 is ⌊(d1 + d2)/2⌋-linked for d1, d2 ≥ 2, and this is best possible.

This result is connected to graphs of simple polytopes. The Cartesian product Kd1+1 × Kd2+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 simple polytope, a (d1 + d2)-dimensional polytope in which every vertex is incident to exactly d1 + d2 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.


k-linked, cyclic polytope, connectivity, dual polytope, linkedness, Cartesian product

Full Text:



ISSN: 1855-3974

Issues from Vol 6, No 1 onward are partially supported by the Slovenian Research Agency from the Call for co-financing of scientific periodical publications