字母重叠图的一些指标

论文摘要

无向de Bruijn图常被用作通讯网络模型。它具有高效网络应该具有的许多特性，如短直径，小最大度和多结点。我们研究了一类比无向de Bruijn图更广泛的图，字母重叠图G（k，d，s）。它的顶点集V={v|v=（v1，…，vk）；vi∈{1，2，…，d}（1≤i≤k）}，任意两个不同的顶点u=（u1，…，uk），v=（v1，…，vk）之间有边当且仅当ui+s=vi（1≤i≤k-s）或者vi+s=vi（1≤i≤k-s）。在此定义下，当s=1时，字母重叠图恰是无向de Bruijn图。在本文中，我们得到了字母重叠图G（k，d，s）的以下结果：给出了G（k，d，s）的顶点度表达式，计算出直径和围长分别为[k/s]和3，构造了ds+1个自同构。当s≥k/2时，证明了G（k，d，s）的连通度为2ds-2dk-2t，并且是超边连通的。

论文目录

• 摘要
• ABSTRACT（英文摘要）
• 第一章 引言
• 1.1 基本概念和记号
• 1.2 本文涉及图的一些相关结论
• 1.2.1 连通度
• 1.2.2 超边连通性
• 1.3 研究结果
• 1.3.1 de Bruijn图的结果
• 1.3.2 字母重叠图的结果
• 第二章 字母重叠图G（k,d,s）的顶点度,直径和围长
• 2.1 引言
• 2.2 顶点度
• 2.3 图G（k,d,s）的直径和围长
• 第三章 图G（k,d,s）（s≥k/2）的连通度
• 3.1 图G（k,d,s）（s≥k/2）的子图结构
• 3.2 图G（k,d,s）（s≥k/2）的连通度
• 第四章 图G（k,d,s）（s≥k/2）的超边连通性及自同构
• 4.1 图G（k,d,s）（s≥k/2）的边连通度
• 4.2 图G（k,d,s）（s≥k/2）的超边连通性
• 4.3 图G（k,d,s）的自同构
• 参考文献
• 致谢