Abstract
Assume that u and v are any two distinct vertices of different partite sets of S{n} with n ≥ 5. We prove that there are (n-1) internally disjoint paths P₁, P₂, ..., P{n-1} joining u to v such that \bigcup\nolimits_{i = 1}^{n - 1} P{i} spans S{n} and l(P{i}) ≤ (n - 1)! + 2(n - 2)! + 2(n - 3)! + 1 = \frac{{n!}}{{n - 2}} + 1. We also prove that there are two internally disjoint paths Q₁ and Q₂ joining u to v such that Q₁ ∪ Q₂ spans S{n} and l(Q₁) ≤ \frac{{n!}}{2} + 1 for i = 1, 2.