- 토러스의 일대일 서로소인 경로 커버
- ㆍ 저자명
- 김희철,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$.