On the spanning w-wide diameter of the star graph

✍ Scribed by Cheng-Kuan Lin; Hua-Min Huang; D. Frank Hsu; Lih-Hsing Hsu

• Publisher: John Wiley and Sons
• Year: 2006
• Tongue: English
• Weight: 402 KB
• Volume: 48
• Category: Article
• ISSN: 0028-3045
• DOI: 10.1002/net.20135

✦ Synopsis

Abstract

Let u and v be any two distinct nodes of an undirected graph G, which is k‐connected. A container C(u,v) between u and v is a set of internally disjoint paths {P~1~,P~2~,…,P~w~} between u and v where 1 ≤ w ≤ k. The width of C(u,v) is w and the length of C(u,v) {written as l____C(u,v) is max { l(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 { l(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!\over 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 ${n!\over 2}+1$. © 2006 Wiley Periodicals, Inc. NETWORKS, Vol. 48(4), 235–249 2006