Linkedness of Cartesian products of complete graphs
Keywords:k-linked, cyclic polytope, connectivity, dual polytope, linkedness, Cartesian product
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.
Articles in this journal are published under Creative Commons Attribution 4.0 International License