( n , k ) - 스타 그래프의 사이클 특성 = Cycle Property in the (n,k)-star Graph

다국어 초록 (Multilingual Abstract)

In this paper, we analyze the cycle property of the (n,k)-star graph that has an attention as an alternative interconnection network topology in recent years. Based on the graph-theoretic properties in (n,k)-star graphs, we show the pancyclic property of the graphs and also present the corresponding algorithm. Based on the recursive structure of the graph, we present such top-down approach that the resulting cycle can be constructed by applying series of "dimension expansion" operations to a kind of cycles consisting of sub-graphs. This processing naturally leads to such property that the resulting cycles tend to be integrated compactly within some minimal subset of sub-graphs, and also means its applicability to another classes of the disjoint-style cycle problems. This result means not only the graph-theoretic contribution of analyzing the pancyclic property in the underlying graph model but also the parallel processing applications such as message routing or resource allocation and scheduling in the multi-computer system with the corresponding interconnection network.