The detour \(d(i, j)\) between vertices \(i\) and \(j\) of a graph is the number of edges of the longest path connecting these vertices. The matrix whose \((i, j)\)-entry is the detour between vertices \(i\) and \(j\) is called the detour matrix. The half sum \(D\) of detours between all pairs of vertices (in a connected graph) is the detour index, i.e.,