Global efficiency of graphs

Abstract

The distance d(i,j) between any two vertices i and j in a graph is the number of edges in a shortest path between i and j. If there is no path connecting i and j, then 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 i and j is defined to be ∈i,j=1d(i,j) for all i≠j. The global efficiency of a graph is the average efficiency over all i≠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,n, star and subdivided star graphs, and the Cartesian Products Kn×Pnm, Kn×Cnm, Km×Kn, and Pm×Pn.

Keywords

• Distance
• Efficiency
• Harary index