標題: On the spanning w-wide diameter of the star graph 作者: Lin, Cheng-KuanHuang, Hua-MinHsu, D. FrankHsu, Lih-Hsing資訊工程學系Department of Computer Science 關鍵字: diameter;hamiltonian;hamiltonian laceable;star graphs 公開日期: 1-Dec-2006 摘要: Let a and v be any two distinct nodes of an undirected graph G, which is k-connected. A container C(u, v) between a and v is a set of internally disjoint paths {P(1), P(2),..., P(W)} between a and v where 1 <= w <= k. The width of C(u, v) is w and the length of C(u, v) {written as I[C(u, v)]} is max{I(P(i)) 1 <= I <= w}. A w-container C(u, v) is a container with width w. The w-wide distance between u and v, d(w)(u, v), is min{I(C(u, v)) C(u, v) is a w-container). A w-container C(u, v) of the graph G is a w*-container if every node of G is incident with a path in C(u, v). That means that the w-container C(u, v) spans the whole graph. Let S(n) be the n-dimensional star graph with n >= 5. It is known that S(n) is bipartite. In this article, we show that, for any pair of distinct nodes u and v in different partite sets of S(n), there exists an (n - 1)*-container C(u, v) and the (n - 1)-wide distance d((n-1))(u, v) is less than or equal to n!/n-2 + 1. In addition, we also show the existence of a 2*-container C(u, v) and the 2-wide distance d(2)(u, v) is bounded above by nI/2 + 1. (C) 2006 Wiley Periodicals, Inc. URI: http://dx.doi.org/10.1002/net.20135http://hdl.handle.net/11536/11469 ISSN: 0028-3045 DOI: 10.1002/net.20135 期刊: NETWORKS Volume: 48 Issue: 4 起始頁: 235 結束頁: 249 Appears in Collections: Articles

Files in This Item: