The Detour Matrix

The detour matrix (or the maximum path matrix) of a vertex-labeled connected graph G, denoted by DM, is a real symmetric VxVmatrix whose elements are defined as (Harary, 1971 Buckley and Harary, 1990 Amic and Trinajstid, 1995, Trinajstid et al., 1997a Nikolic et al., 1999 Todeschini and Consonni, 2000, 2009) 

Rucker and Riicker (1998) proposed a slightly different definition of the detour matrix. These authors pointed out that it was never well explained by either Harary (1971) or others (e.g.. Amid and Trinajstid, 1995) why zeros should appear as diagonal elements of the detour matrix. They therefore defined the diagonal elements of the detour matrix as the lengths of the shortest self-returning walks (iirw), 

FIGURE 4.4 Two pairs of nonisomorphic graphs, Gip-G o and G21-G22, with identical detour matrices. 

Several methods are available for computing the detour matrix. We list three here  

The paper-and-pencil approach of path tracing on a graph G, which can be carried out by hand (Amic and Trinajstic, 1995) or with a computer (Lukovits and Razinger, 1997 Trinajstic et al., 1997b) 

---

Two matrices are particularly important, both of them based on the topological distance between vertices within a graph the distance matrix D(G) and the detour matrix A(G). The first contains as values the smallest number of steps from vertex i to vertex j, and the second contains as values the longest paths. For example, Equation (6.5) shows the D and A matrices of the DIOP ligand. 

The detour matrix A of a graph 5 (or maximum path matrix) is a square symmetric Ax A matrix, A being the number of graph vertices, whose entry i-j is the length of the longest path from vertex v, to vertex Vy [Buckley and Harary, 1990 Ivanciuc... 

From the distribution of the element values in the i th row of the detour matrix, the maximum path degree sequence of the i th vertex is derived as a local vector-descriptor defined as ... 

The characteristic polynomial of the detour matrix is called the detour polynomial and is defined as ... 

Each entry i-j of the Ap matrix is calculated from the detour matrix A as the following ... 

From the detour matrix and the distance matrix, a combined matrix, called detour/ distance matrix A/D (or maximum/minimum path matrix), is defined as [Ivanciuc and Balaban, 1994b] ... 

It is a square unsymmetric Ax A matrix, where the upper triangle of the matrix contains the elements of the detour matrix (information about the longest paths) and the lower triangle contains the elements of the topological distance matrix (information about the shortest paths). 

The maximum/minimum path sum of the i th vertex, denoted by MmPVS, is a local vertex invariant defined as the sum of the lengths of the longest and shortest paths between vertex v, and any other vertex in the molecular graph. It is calculated as the sum of elements over the / th row and / th column in the A/D matrix, or, alternatively, as the sum of the - vertex distance degree o, calculated on the distance matrix D and the maximum path sum MPVS, of the / th vertex calculated on the detour matrix A ... 

Opposite to the distance matrix is the detour matrix, where the entries correspond to the length of the longest path between the vertices. Other related topological matrices are the -> distance/distance matrix, the - detour/distance matrix and the - dis-tance/detour quotient matrix. 

Amic, D. and Trinajstic, N. (1995c). On the Detour Matrix. Croat.Chem.Acta, 68,53-62. 

Nikolic, S., TWnajstic, N., Juric, A. and Mihalic, Z. (1996a). The Detour Matrix and the Detour Index of Weighted Graphs. Croat. Chem.Acta, 69,1577-1591. 

Rucker, G. and Rucker, C. (1998). Symmetry-Aided Computation of the Detour Matrix and the Detour Index. J.Chem.lnf.Comput.ScL, 38,710-714. 

Criterion IP = minimum —> vertex path eccentricity (i.e., the largest distance from the ith vertex in the detour matrix) ... 

The detour polynomial is the characteristic polynomial of the —> detour matrix A of the molecular graph ]Nikolic, Trinajstic et al, 1999b] ... 

Difference indices were proposed as the difference between topological descriptors obtained from the —> distance matrix D and the —> detour matrix A they are defined as [Castro, Tueros et al., 2000]... 

The detour-delta matrix, denoted as A, is another combinatorial matrix derived as the difference between the detour-path matrix Ap and the detour matrix A [Janezic, Milicevic... 

Nikolic, S Trinajstic, N. and Mihalic, Z. (1999b) The Detour matrix and the Detour index, in Topological Indices and Related Descriptors in QSAR and QSPR (eds J. Devillers and A.T. Balaban), Gordon and Breach Science Publishers, Amsterdam,... 

While the standard distance matrix determines a graph uniquely, this is not the case with the detour matrix—there are nonisomorphic graphs with identical detour matrices. Two pairs of such graphs, taken from Randid et al. (1998), are shown in Figure 4.4. 

We present here the second method by which the detour matrix of a polycyclic graph can be generated from the vertex-distance matrices of the corresponding spanning trees following the procedure consisting of the three steps outlined below (Trinajstic et al 1997a Nikolid et al., 1990,1996) ... 

Setting up the detour matrix of G by matching the vertex-distance matrices of spanning trees, selecting only those elements that possess the largest numerical values, and placing them in the appropriate place in the detour matrix. 

Matching these four vertex-distance matrices and choosing the appropriate elements leads to the detour matrix of Gj that was presented above. It should also be pointed out that the vertex-distance matrix and the detour matrix are identical for acyclic graphs. 

The detour matrix was used to generate a Wiener-like index (Amid and Trinajstic, 1995), named the detour index (Lukovits, 1996), for simple and weighted graphs (Amid and Trinajstid, 1995 Nikolid et al 1990, 1996, 1999 Lukovits, 1996 Trinajstid et al., 1997a, 1997b, 2001 Lukovits and Razinger, 1997). All kinds of distance indices can be generated from the detour matrix (Lukovits, 1996 Nikolid et al., 1999 Todeschini and Consonni, 2000, 2009 Ludid et al., 2001 Randid and Pompe, 2001 Trinajstid et al, 2001). 

THE VERTEX-DISTANCE MATRIX AND THE DETOUR MATRIX OF COMPLETE GRAPHS AND COMPLETE BIPARTITE GRAPHS... 

In the case of the complete bipartite graphs Kyo y the off-diagonal elements of the detour matrix are all equal to V 1 or V- 2, depending on whether vertices are connected or not ... 

---