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

Edge-fault-tolerant Bipanconnectivity of Complete Bipartite Graph K_(n,n) and Panconnectivity of Complete k-partite Graph K_(n,n,…,n)(k≥3)

图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是泛连通的.

A graph G is called panconnected if for any two vertices x and y,there exists a path connecting x and y of any length l with d（x,y） ≤ l ≤ ︱V（G）︱ -1,where d（x,y） denotes the distance between x and y;A graph G is called bipanconnected if for any two vertices x and y,there exists a path connecting x and y of any length l with d（x,y） ≤ l ≤ ︱V（G）︱- 1 and l-d（x,y） is even.In this paper,we apply induction to prove the following conclusions.when n ≥ 2,In complete bipartite graph K n,n, the number of faulty edges Fe ≤ n-2,then K n,n-Fe is bipanconnected,Moreover,the number n-2 of faulty edges tolerated is sharp;complete k-partite graph K n,n,L,n（k ≥ 3）is panconnected.