On the spanningw‐wide diameter of the star graph
Cheng‐Kuan Lin, Hua‐Min Huang, D. Frank Hsu, Lih‐Hsing Hsu · Networks · 2006
Abstract Letuandvbe any two distinct nodes of an undirected graphG, which isk‐connected. A containerC(u,v) betweenuandvis a set of internally disjoint paths {P1,P2,…,Pw} betweenuandvwhere 1 ≤w≤k. The width ofC(u,v) iswand the length ofC(u,v) {written aslC(u,v) is max {l(Pi) ∣ 1 ≤i≤w}. Aw‐containerC(u,v) is a container with widthw. Thew‐wide distance betweenuandv,dw(u,v), is min {l(C(u,v)) ∣C(u,v) is aw‐container}. Aw‐containerC(u,v) of the graphGis aw*‐container if every node ofGis incident with a path inC(u,v). That means that thew‐containerC(u,v) spans the whole graph. LetSnbe then‐dimensional star graph withn≥ 5. It is known thatSnis bipartite. In this article, we show that, for any pair of distinct nodesuandvin different partite sets ofSn, there exists an (n− 1)*‐containerC(u,v) and the (n− 1)‐wide distanced(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*‐containerC(u,v) and the 2‐wide distanced2(u,v) is bounded above by${n!\over 2}+1$ . © 2006 Wiley Periodicals, Inc. NETWORKS, Vol. 48(4), 235–249 2006