- 고장난 재귀원형군의 사이클 임베딩
- ㆍ 저자명
- 박정흠
- ㆍ 간행물명
- 정보과학회논문지. Journal of KIISE. 시스템 및 이론
- ㆍ 권/호정보
- 2004년|31권 1호|pp.86-94 (9 pages)
- ㆍ 발행정보
- 한국정보과학회
- ㆍ 파일정보
- 정기간행물| PDF텍스트
- ㆍ 주제분야
- 기타
이 논문은 한국과학기술정보연구원과 논문 연계를 통해 무료로 제공되는 원문입니다.
이 논문에서는 재귀원형군 $ G(2^m, 4), m{geq}3$은 고장인 요소의 수가 m-2개 이하일 때, 임의의 1, 4 ${leq}1{leq}2^m-f_v$에 대하여 길이 1인 고장 없는 사이클을 가짐을 보인다. 여기서, f$_{v}$ 는 고장 정점의 수이다. 이를 위하여, ｜F｜$leq$k인 임의의 고장 요소 집합 F에 대해서 G-F가 임의의 두 정점을 잇는 길이가 해밀톤 경로보다 하나 작은 경로를 가질 때, G를 k-고장 하이포해밀톤 연결된 그래프라고 정의하고, $ G(2^m, 4), m{geq}3$은 m-3-고장 하이포해밀톤 연결된 그래프임을 보인다.
In this paper, we show that $ G(2^m, 4), m{geq}3$with at most m-2 faulty elements has a fault-free cycle of length 1 for every ${leq}1{leq}2^m-f_v$ is the number of faulty vertices. To achieve our purpose, we define a graph G to be k-fault hypohamiltonian-connected if for any set F of faulty elements, G- F has a fault-free path joining every pair of fault-free vertices whose length is shorter than a hamiltonian path by one, and then show that$ G(2^m, 4), m{geq}3$ is m-3-fault hypohamiltonian-connected.