Linkedness of Cartesian products of complete graphs

No author found.

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} i m e s K^{d_{2} + 1}

of complete graphs

K^{d_{1} + 1}

and

K^{d_{2} + 1}

is

f l o o r (d_{1} + d_{2}) / 2

-linked for

d_{1}, d_{2} g e 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} i m e s K^{d_{2} + 1}

is the graph of the Cartesian product

T (d_{1}) i m e s 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}) i m e s 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

f l o o r 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.

Cites Work