본문 바로가기
HOME> 논문 > 논문 검색상세

논문 상세정보

제한된 HL-그래프와 재귀원형군 $G(2^m,4)$에서 매칭 배제 문제
Matching Preclusion Problem in Restricted HL-graphs and Recursive Circulant $G(2^m,4)$

박정흠   (가톨릭대학교 컴퓨터정보공학부UU0000012  );
  • 초록

    그래프의 매칭 배제 집합은 그것을 삭제한 그래프가 완전 매칭이나 준완전 매칭을 가지지 않는 에지 집합이다. 매칭 배제수는 모든 매칭 배제 집합의 최소 크기이다. 이 논문에서는 임의의 $m{\geq}4$ 에 대하여 H-차원 제한된 HL-그래프와 재귀원형군 $G(2^m,4)$ 의 매칭 배제수는 분지수 m과 같고, 모든 최소 매칭 배제 집합은 한 정점에 인접한 에지 집합임을 보인다.


    The matching preclusion set of a graph is a set of edges whose deletion results in a graph that has neither perfect matchings nor almost perfect matchings. The matching preclusion number is the minimum cardinality over all matching preclusion sets. We show in this paper that, for any $m{\geq}4$ , the matching preclusion numbers of both m-dimensional restricted HL-graph and recursive circulant $G(2^m,4)$ are equal to degree m of the networks, and that every minimum matching preclusion set is the set of edges incident to a single vertex.


  • 주제어

    완전 매칭 .   준완전 매칭 .   에지 고장 .   고장 감내 .   고장 해밀톤 성질 .   상호연결망.  

  • 참고문헌 (10)

    1. R.C. Brigham, F. Harary, E.C. Violin, J. Yellen, "Perfect-matching preclusion," Congressus Numerantium 174, pp. 185-192, 2005 
    2. J.-H. Park, H.-S. Lim, and H.-C. Kim, "Panconnectivity and pancyclicity of hypercube-like interconnection networks with faulty elements," Theoretical Computer Science 377, pp. 170-180, 2007 
    3. J.-H. Park and K.Y. Chwa, "Recursive circulants and their embeddings among hypercubes," Theoretical Computer Science 244, pp. 35-62, 2000 
    4. J.-H. Park, "Panconnectivity and edge-pancyclicity of faulty recursive circulant $G(2^m,4)$," Theoretical Computer Science, 390, pp. 70-80, 2008 
    5. D.A. Reed and R.M. Fujimoto, Multicomputer Networks: Message-Based Parallel Processing, The MIT Press, 1987 
    6. D. Kratsch, T. Kloks, and H. Muller, "Measuring the vulnerability for classes of intersection graphs," Discrete Applied Mathematics 77, pp. 259-270, 1997 
    7. J.-H. Park, H.-C. Kim, and H.-S. Lim, "Fault- hamiltonicity of hypercube-like interconnection networks," in Proc. of the IEEE International Parallel & Distributed Processing Symposium IPDPS 2005, Apr. 2005 
    8. A.-H. Esfahanian, "Generalized measures of fault tolerance with application to n-cube networks," IEEE Trans. Computers 38(11), pp. 1586-1591, 1989 
    9. E. Cheng and L. Liptak, "Matching preclusion for some interconnection networks," Networks 50, pp. 173-180, 2007 
    10. C.-H. Tsai, J.M. Tan, Y.-C. Chuang, and L.-H. Hsu, "Fault-free cycles and links in faulty recursive circulant graphs," in Proc. of Workshop on Algorithms and Theory of Computation ICS2000, pp. 74-77, 2000 

 저자의 다른 논문

  • 박정흠 (20)

    1. 1999 "재귀원형군의 위상 특성 : 서로소인 사이클과 그래프 invariant" 정보과학회논문지. Journal of KISS (a):computer systems and theory. A 26 (8): 999~1007    
    2. 1999 "재귀원형군의 위상 특성 : 서로소인 경로" 정보과학회논문지. Journal of KISS (a):computer systems and theory. A 26 (8): 1009~1023    
    3. 2000 "m과 n이 짝수인 이중 루프 네트워크 G(mn;1,m)의 고장 해밀톤 성질" 정보과학회논문지. Journal of KIISE. 시스템 및 이론 27 (10): 868~879    
    4. 2001 "재귀원형군의 강한 해밀톤 성질" 정보과학회논문지. Journal of KIISE. 시스템 및 이론 28 (8): 399~405    
    5. 2002 "재귀원형군과 하이퍼큐브의 고장 감내에 대한 결정적 척도" 정보과학회논문지. Journal of KIISE. 시스템 및 이론 29 (9): 493~502    
    6. 2002 "재귀원형군 $G(2^{m},2^{k})$의 고장 지름" 정보과학회논문지. Journal of KIISE. 시스템 및 이론 29 (12): 665~679    
    7. 2003 "재귀원형군의 일대일 서로소인 경로 커버" 정보과학회논문지. Journal of KIISE. 시스템 및 이론 30 (12): 691~698    
    8. 2004 "이분 그래프인 이중 루프 네트워크의 고장 해밀톤 성질" 정보과학회논문지. Journal of KIISE. 시스템 및 이론 31 (1): 19~26    
    9. 2004 "고장난 재귀원형군의 사이클 임베딩" 정보과학회논문지. Journal of KIISE. 시스템 및 이론 31 (1): 86~94    
    10. 2006 "하이퍼큐브형 상호연결망의 비쌍형 다대다 서로소인 경로 커버" 정보과학회논문지. Journal of KIISE. 시스템 및 이론 33 (10): 789~796    

 활용도 분석

  • 상세보기

    amChart 영역
  • 원문보기

    amChart 영역

원문보기

무료다운로드
  • NDSL :
유료다운로드

유료 다운로드의 경우 해당 사이트의 정책에 따라 신규 회원가입, 로그인, 유료 구매 등이 필요할 수 있습니다. 해당 사이트에서 발생하는 귀하의 모든 정보활동은 NDSL의 서비스 정책과 무관합니다.

원문복사신청을 하시면, 일부 해외 인쇄학술지의 경우 외국학술지지원센터(FRIC)에서
무료 원문복사 서비스를 제공합니다.

NDSL에서는 해당 원문을 복사서비스하고 있습니다. 위의 원문복사신청 또는 장바구니 담기를 통하여 원문복사서비스 이용이 가능합니다.

이 논문과 함께 출판된 논문 + 더보기