Global efficiency of graphs

The distance d(i,j)d(i,j) between any two vertices ii and jj in a graph is the number of edges in a shortest path between ii and jj. If there is no path connecting ii and jj, then d(i,j)=∞d(i,j)=∞. In 2001, Latora and Marchiori introduced the measure of efficiency between vertices in a graph (Latora and Marchiori, 2001). The efficiency between two vertices ii and jj is defined to be ∈i,j=1d(i,j) for all i≠ji≠j. The global efficiency   of a graph is the average efficiency over all i≠ji≠j. The concept of global efficiency has been applied to optimization of transportation systems and brain connectivity. In this paper we determine the global efficiency for complete multipartite graphs Km,nKm,n, star and subdivided star graphs, and the Cartesian Products Kn×Pnm, Kn×Cnm, Km×KnKm×Kn, and Pm×PnPm×Pn.