完全二部图K_(n,n)的容错偶泛连通性和完全k(k≥3)部图K_(n,n,…,n)的泛连通性

作者：王超越

来源：漳州师范学院学报(自然科学版), 2011, (03): 1-3.

DOI：10.16007/j.cnki.issn2095-7122.2011.03.023

• 泛连通性
• 偶泛连通性
• 边容错
• 完全二部图
• 完全多部图 Panconnectivity
• Bipanconnectivity
• Edge fault-tolerant
• Complete bipartite graph
• Complete multipartite graph.

图G称为泛连通的,如果对于G中距离为d(x,y)的任意两点x和y,G中都存在每个长为l的x:y路(这里d(x,y)≤l≤︱V(G)︱-1);图G称为偶泛连通的,如果对于G中距离为d(x,y)的任意两点x和y,G中都存在每个长为l的x: y路(这里d(x,y)≤l≤︱V(G)︱-1),且l和d(x,y)有相同的奇偶性.本文用归纳法证明了以下结论:当n≥2时,在完全二部图K n,n中,若故障边数︱Fe︱≤n-2,则K n,n-Fe是偶泛连通的,并且︱Fe︱的上界n-2是最优的;完全k(k≥3)部图K n,n,…,n是泛连通的.

• 单位
  闽南师范大学