无向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，并且是超边连通的。
本文来源: https://www.lw50.cn/article/c4cf0f4a773c000a2c17d64e.html