论文标题
完整图的笛卡尔产品的连接性
Linkedness of Cartesian products of complete graphs
论文作者
论文摘要
本文涉及完整图的笛卡尔产品的联系。如果每组以任意$ k $ k $ k $的顶点组织的$ 2K $差异的$ 2K $链接}的图表为{\ it $ k $链接}，则有$ k $ k $ vertex-disjoint路径在成对中加入Vertices。 我们表明，笛卡尔产品$ k^{d_ {1} +1} \ times k^{d_ {2} +1} $的完整图的$ $ d_ {1}，d_ {2} \ ge 2 $，这是最好的。 ％的polytope被称为{\ it $ k $链接}，如果其图为$ k $ - 链接。 该结果连接到简单多面体的图。笛卡尔产品$ k^{d_ {1} +1} \ times k^{d_ {2} +1} $是笛卡尔产品$ t（d_ {1}）\ times t（d_ {1}）\ times t（d_ {2}）$ d_ {1} $ d_ {1} $ - d_ {1} $ d_ $ d_ $ d_ $ d_ $ d_ $ d y;单纯$ t（d_ {2}）$。 polytope $ t（d_ {1}）\ times t（d_ {2}）$是一个简单的polytope}，一个$（d_ {1}+d_ {2}）$ - 尺寸多型，每个顶点在每个顶点中都是$ d _ {1}+d_ {1}+d_ {2} $ edges。 虽然并非每个$ d $ -polytope都是$ \ floor {d/2} $ - 可以猜想每个简单的$ d $ -polytope是。我们的结果意味着对两种简单的笛卡尔产品进行了修订的猜想的真实性。
This paper is concerned with the linkedness of Cartesian products of complete graphs. A graph with at least $2k$ vertices is {\it $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}+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}\ge 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.
