On the spanning w-wide diameter of the star graph

Abstract

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.