기관회원 [로그인]
소속기관에서 받은 아이디, 비밀번호를 입력해 주세요.
개인회원 [로그인]

비회원 구매시 입력하신 핸드폰번호를 입력해 주세요.
본인 인증 후 구매내역을 확인하실 수 있습니다.

회원가입
서지반출
토러스의 일대일 서로소인 경로 커버
[STEP1]서지반출 형식 선택
파일형식
@
서지도구
SNS
기타
[STEP2]서지반출 정보 선택
  • 제목
  • URL
돌아가기
확인
취소
  • 토러스의 일대일 서로소인 경로 커버
저자명
김희철,Kim. Hee-Chul
간행물명
정보과학회논문지. Journal of KIISE. 시스템 및 이론
권/호정보
2011년|38권 1호|pp.49-58 (10 pages)
발행정보
한국정보과학회
파일정보
정기간행물|
PDF텍스트
주제분야
기타
이 논문은 한국과학기술정보연구원과 논문 연계를 통해 무료로 제공되는 원문입니다.
서지반출

기타언어초록

그래프에서 두 정점 u, ${upsilon}$ 사이의 경로들이 u와 ${upsilon}$를 제외한 다른 정점을 중복해서 지나지 않을 때 이 u, ${upsilon}$사이의 경로들을 정점이 서로소 (vertex disjoint)인 경로들이라 한다. 양의 정수 k에 대하여, 그래프 G의 두 정점 u, ${upsilon}$사이의 정점이 서로소인 k개의 경로들이 G의 모든 정점을 지나면 이들 경로를 u와 ${upsilon}$사이의 정점이 서로소인 k-경로 커버라 한다. G의 모든 두 정점 u와 ${upsilon}$사이에 정점이 서로소인 k-경로 커버가 존재할 때 G를 일대일 k-경로 커버 가능(one-to-one k-path coverable)하다고 한다. 그래프 G가 일대일 k-경로 커버 가능하려면 $k{leq}{kappa}(G)$이다. 여기서 ${kappa}(G)$는 G의 연결도이다. 연결도 ${kappa}(G)$가 3이상인 이분 그래프 G는 모든 $3{leq}k{leq}{kappa}(G)$에 대하여, 같은 이분분할 집합의 두 정점 사이에 정점이 서로소인 k-경로 커버가 존재하지 않는다. 본 논문에서는 이분 그래프가 아닌 토러스의 k-경로커버를 연구한다. $d({geq}2)$-차원 토러스의 연결도는 2d 인데, 이 논문에서는 이분 그래프가 아닌 $d({geq}2)$-차원 토러스는 모든 $1{leq}k{leq}2d$에 대하여 일대일 k-경로 커버 가능함을 보인다.

기타언어초록

Let u and ${upsilon}$ be any two vertices of a graph G and k be a positive integer. A vertex disjoint k-path cover between u and ${upsilon}$ is a set of k vertex disjoint paths between u and ${upsilon}$ such that these paths contain all vertices of G and there do not exist common vertices except u and ${upsilon}$ in these paths. A graph G is called one-to-one k-path coverable if for any two vertices u and ${upsilon}$, there is a vertex disjoint k-path cover between u and ${upsilon}$. It is known that in the bipartite graph G with 3 or more connectivity, there is no vertex disjoint k-path cover between two vertices which belong to the same bipartite set for any $3{leq}k{leq}{kappa}(G)$ where ${kappa}(G)$ is connectivity of G. In this paper, we study k-path coverability of the torus which is one of the well known interconnection networks. The non-bipartite $d({geq}2)$-dimensional torus G is shown to be one-to-one k-path coverable for any $1{leq}k{leq}{kappa}(G)$ where ${kappa}(G)=2d$.