有關(guān)加強(qiáng)超立方體泛連通性的證明

范漪涵 劉紅美

【摘要】 在本論文中，我們研究容錯(cuò)加強(qiáng)超立方體Qn，k中的路和圈的嵌入問(wèn)題.我們利用已知的結(jié)論當(dāng)n（≥3）和k有相同奇偶性時(shí)，Qn，k-{f}包含一個(gè)長(zhǎng)為4到2n-2容錯(cuò)偶泛圈；進(jìn)一步地，我們證得當(dāng)n和k有相同奇偶性時(shí)，Qn，k（1≤k≤n-1）是偶泛連通的.

【關(guān)鍵詞】 加強(qiáng)超立方體；偶泛連通性；哈密頓連通性

1.引言

在互聯(lián)網(wǎng)絡(luò)中，一個(gè)網(wǎng)絡(luò)是否可以被另一個(gè)網(wǎng)絡(luò)模擬是非常重要的，這就是我們所說(shuō)的嵌入問(wèn)題.

超立方體Qn是現(xiàn)如今最受歡迎的互聯(lián)網(wǎng)絡(luò)之一.它具有很多優(yōu)良的性質(zhì)，如可嵌入性、可遷性、對(duì)稱性、正則性、遞歸性等.關(guān)于折疊超立方體的一些性質(zhì)前人已做了很多的研究.然而，對(duì)于更一般的形式，加強(qiáng)超立方體的研究卻比較少，我們主要證明了：當(dāng)n和k有相同的奇偶性時(shí)，n維加強(qiáng)超立方體Qn，k是偶泛連通的.

2.預(yù)備知識(shí)

下面給出一些對(duì)于我們的主要證明很重要的一些引理.