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

논문 상세정보

정보과학회논문지. Journal of KIISE. 시스템 및 이론 v.30 no.12, 2003년, pp.691 - 698   피인용횟수: 4
본 등재정보는 저널의 등재정보를 참고하여 보여주는 베타서비스로 정확한 논문의 등재여부는 등재기관에 확인하시기 바랍니다.

재귀원형군의 일대일 서로소인 경로 커버
One-to-One Disjoint Path Covers in Recursive Circulants

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

    이 논문에서는 주어진 두 정점 사이에 다른 모든 정점을 정확히 한번 지나는 k개의 서로소인 경로가 존재하는가 하는 일대일 서로소인 경로 커버 문제를 제안한다. 임의의 k, 임의의 두 정점 사이에 일대일 서로소인 경로 커버를 가지는 그래프는 해밀톤 연결되어 있다는 것보다 강한 해밀톤 성질을 가진다. 재귀원형군에서 이 문제를 고찰하여, 임의의 $k(1{\leq}k{\leq}m)$ 에 대해서 $ G(2^m,4)$ , $m{\geq}3$ 은 임의의 두 정점 사이에 k개의 경로로 이루어진 일대일 서로소인 경로 커버가 존재함을 보인다.


    In this paper, we propose a problem, called one-to-one disjoint path cover problem, whether or not there exist k disjoint paths joining a pair of vertices which pass through all the vertices other than the two exactly once. A graph which for an arbitrary k, has a one-to-one disjoint path cover between an arbitrary pair of vertices has a hamiltonian property stronger than hamiltonian-connectedness. We investigate this problem on recursive circulants and prove that for an arbitrary k $k(1{\leq}k{\leq}m)$ $ G(2^m,4)$ , $m{\geq}3$ , has a one-to-one disjoint path cover consisting of k paths between an arbitrary pair of vortices.


  • 주제어

    서로소인 경로 .   경로 커버 .   강한 해밀톤 성질 .   재귀원형군.  

  • 참고문헌 (16)

    1. 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 
    2. M.E. Muzychuk and G. Tinhof, 'Recognizing circulant graphs in polynomial time: An application of association schemes,' The Electronic Journal of Combinatorics, vol. 8, #R26, 2001 
    3. G. Fertin and A. Raspaud, 'Recognizing Recursive Circulant Graphs G(cd^m,d),' preprint 2002 
    4. Y.-C. Chen, J.J.M. Tan, L.-H. Hsu, and S.-S. Kao, 'Super-connectivity and super-edge-connectivity for some interconnection networks,' Applied Mathematics and Computation, vol. 140, pp. 245-254, Aug. 2003 
    5. T. Araki and Y. Shiba, 'Pancyclicity of recursive circulant graphs,' Information processing Letters, vol. 81, pp. 187-190, Feb. 2002 
    6. J.-H. Park, 'Hamiltonian decomposition of recursive circulants,' International Symposium on Algorithms and Computation ISAAC'98 (LNCS #1533), Taejon, Korea, pp. 297-306, Dec. 1998 
    7. D.K.Biss, 'Hamiltonian decomposition of recursive circulant graphs,' Discrete Mathematics, vol. 214, pp. 89-99, Mar. 2000 
    8. C. Micheneau, 'Disjoint Hamiltonian cycles in recursive circulant graphs,' Information Processing Letters, vol. 61, pp. 259-264, Mar. 1997 
    9. H.-S. Lim, J.-H. Park and K.-Y. Chaw, 'Embedding trees into recursive circulants,' Discrete Applied Mathematics, vol. 69, pp. 83-99, 1996 
    10. C. Kim, J. Choi and H.-S. Lim, 'Embedding Full Ternary Trees into Recursive Circulants.' Lecture Notes in Computer Science 2510, pp. 874-882, 2001 
    11. J.-H. Park and K.-Y. Chwa, 'Recursive circulants and their embeddings among hypercubes,' Theoretical Computer Science, vol. 244, pp. 35-62, Aug. 2000 
    12. H. Enomoto and K. Ota, 'Partitions of a graph into paths with prescribed endvertices and lengths,' Journal of Graph Theory, vol. 34(2), pp. 163-169, June 2000 
    13. F. Harary and M. Lewinter, 'The starlike trees which span a hypercube,' Computers & Mathematics with Applications, vol. 15(4), pp. 299-302, 1988 
    14. D-R. Duh and G.-H. Chen, 'On the Rabin number problem,' Networks, vol. 30(3), pp. 219-230, 1997 
    15. Y. Ishigami, 'The wide-diameter of the n-dimensional toroidal mesh,' Networks, vol. 27, pp. 257-266, 1996 
    16. J.A. Bondy and U.S.R. Murty, Graph Theory with Applications, 5th Printing, American Elsevier Publishing Co. Inc., 1976 
  • 이 논문을 인용한 문헌 (4)

    1. Park Jung-Heum 2005. "Many-to-Many Disjoint Path Covers in Double Loop Networks" 정보과학회논문지. Journal of KIISE. 시스템 및 이론, 32(8): 426~431     
    2. Park, Jung-Heum 2006. "Unpaired Many-to-Many Disjoint Path Covers in Hypercube-Like Interconnection Networks" 정보과학회논문지. Journal of KIISE. 시스템 및 이론, 33(10): 789~796     
    3. Park, Jung-Heum 2007. "Conditions for Disjoint Path Coverability in Proper Interval Graphs" 정보과학회논문지. Journal of KIISE. 시스템 및 이론, 34(10): 539~554     
    4. Kim, Hee-Chul 2011. "One-to-one Disjoint Path Cover of Tori" 정보과학회논문지. Journal of KIISE. 시스템 및 이론, 38(1): 49~58     

 저자의 다른 논문

  • 박정흠 (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. 2004 "이분 그래프인 이중 루프 네트워크의 고장 해밀톤 성질" 정보과학회논문지. Journal of KIISE. 시스템 및 이론 31 (1): 19~26    
    8. 2004 "고장난 재귀원형군의 사이클 임베딩" 정보과학회논문지. Journal of KIISE. 시스템 및 이론 31 (1): 86~94    
    9. 2006 "하이퍼큐브형 상호연결망의 비쌍형 다대다 서로소인 경로 커버" 정보과학회논문지. Journal of KIISE. 시스템 및 이론 33 (10): 789~796    
    10. 2007 "학부 문제해결기법 교과목의 운영 사례" 정보과학회지 = Communications of the Korean Institute of Information Scientists and Engineers 25 (7): 21~25    

 활용도 분석

  • 상세보기

    amChart 영역
  • 원문보기

    amChart 영역

원문보기

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

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

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

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

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