有关加强超立方体泛连通性的证明

范漪涵 刘红美

【摘要】 在本论文中，我们研究容错加强超立方体Qn，k中的路和圈的嵌入问题.我们利用已知的结论当n（≥3）和k有相同奇偶性时，Qn，k-{f}包含一个长为4到2n-2容错偶泛圈；进一步地，我们证得当n和k有相同奇偶性时，Qn，k（1≤k≤n-1）是偶泛连通的.

【关键词】 加强超立方体；偶泛连通性；哈密顿连通性

1.引言

在互联网络中，一个网络是否可以被另一个网络模拟是非常重要的，这就是我们所说的嵌入问题.

超立方体Qn是现如今最受欢迎的互联网络之一.它具有很多优良的性质，如可嵌入性、可迁性、对称性、正则性、递归性等.关于折叠超立方体的一些性质前人已做了很多的研究.然而，对于更一般的形式，加强超立方体的研究却比较少，我们主要证明了：当n和k有相同的奇偶性时，n维加强超立方体Qn，k是偶泛连通的.

2.预备知识

下面给出一些对于我们的主要证明很重要的一些引理.