標題: On the spanning w-wide diameter of the star graph
作者: Lin, Cheng-Kuan
Huang, Hua-Min
Hsu, D. Frank
Hsu, 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.20135
http://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:

  1. 000241963400006.pdf