| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 420554 | Discrete Applied Mathematics | 2009 | 8 Pages |
For two vertices uu and vv in a strong oriented graph DD, the strong distance sd(u,v)sd(u,v) between uu and vv is the minimum size (the number of arcs) of a strong sub-digraph of DD containing uu and vv. For a vertex vv of DD, the strong eccentricity se(v)se(v) is the strong distance between vv and a vertex farthest from vv. The strong diameter sdiam(D)sdiam(D) is the maximum strong eccentricity among the vertices of DD. The lower orientable strong diameter sdiam(G)sdiam(G) of a graph GG is the minimum strong diameter over all strong orientations of GG. An orientation DD of a graph GG is said to be an optimal strong (κ,d)(κ,d)-orientation of GG if κ(D)=⌊κ(G)/2⌋κ(D)=⌊κ(G)/2⌋ and sdiam(D)=sdiam(G)sdiam(D)=sdiam(G), where κ(D)κ(D) (resp. κ(G)κ(G)) is the strong connectivity of DD (resp. connectivity of GG). In this paper, we will show that each complete kk-partite graph has an optimal strong (κ,d)(κ,d)-orientation.
