On the Spanning w-Wide Diameter of the Star Graph*

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 {P1,P2,...,Pw} 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 (Pi) | 1 ≤ i ≤ w}. A w-container C(u,v) is a container with width w. The w-wide distance between u and v, dw (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 Sn be the n-dimensional star graph with n ≥ 5. It is known that Sn is bipartite. In this article, we show that, for any pair of distinct nodes u and v in different partite sets of Sn, 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 d2(u,v) is bounded above by n!2 + 1