On the strong distance problems of pyramid networks

摘要

Suppose G=(V,E) is a graph and D=(V,F) is a strong digraph of G. Let u and v be two vertices of D. The strong distance sd(u,v) is the minimum size of the strong subdigraph of D containing u and v, and the strong eccentricity se(u) is the maximum strong distance sd(u,v) for all vertex v in D. The strong radius and the strong diameter of D are defined as the minimum and maximum strong eccentricity se(u) for all u in D, respectively. In this paper, we present a lower bound of strong diameter (radius) for any strong digraph. Further, we propose a better upper bound of the strong diameter for any Hamiltonian strong digraph. Moreover, we study the strong distance problems on pyramid networks, PM[n]. We give a lower bound to SDIAM(PM[n]) and SRAD(PM[n]). Finally, we conclude the exact value of sdiam(PM[n]), as well as an upper and a lower bound of srad(PM[n]).