초록 close

그래프 G의 고장지름이란 임의의 연결도-1 개 이하의 정점들에 고장이 났을 경우, 모든 두 정점사이의 최단경로 길이의 최대 값을 말한다. 본 논문에서는 k≥3인 재귀원형군 G(2m, 2k)의 고장 지름을 분석한다. dia m,k를 G(2m, 2k)의 지름이라 하자. 2≤m≤k일 때, G(2m, 2k)의 고장지름은 2m - 2이고, m = k +1일 때, 고장지름은 2k -1임을 보인다. 그리고 m > k +1인 재귀원형군 G(2m, 2k)에서, m=1 (mod 2k)이면 고장지름은 dia m,k + 1과 같고,m≠1 (mod 2k)이면 고장지름은 dia m,k + 2 이하임을 보인다.


The fault diameter of a graph G is the maximum of lengths of the shortest paths between all two vertices when there are x(G) - 1 or less faulty vertices, where x(G) is connectivity of G. In this paper, we analyze the fault diameter of recursive circulant G(2m, 2k) with k≥3. Let dia m,k denote the diameter of G(2m, 2k). We show that if 2≤m≤k, the fault diameter of G(2m, 2k) is equal to 2m -1, and if m = k +1, it is equal to 2k -1. It is also shown that for m > k +1, the fault diameter is equal to dia m,k + 1 if m=1 (mod 2k); otherwise, it is less than or equal to dia m,k + 2 .