GRAPHS WITH THE SAME DETOUR MATRIX

The detour matrix (DD) of a graph has for its (ij) entry the length of the longest path between vertices i and j. The sum of all entries abo ve the main diagonal gives the detour index dd. Distinct graphs that h ave the same detour index have been reported in the literature. We exa mined such graphs and others that we have found and report on some of their regularities. We noticed that many graphs have not only the same detour index but also the same detour matrix. We considered in partic ular graphs for which the elements of the detour matrix are maximal. S uch graphs are called saturated graphs. The detour matrix of a saturat ed graph is the same as that of the complete graph having the same num ber or vertices.