RESTRICTED RANDOM-WALKS ON GRAPHS

In the first part of this contribution we outline the construction of a novel matrix associated with a graph, the entries of which give the probability of a random walk over the graph G starting at site i to reach site j in D-ij steps. Here D-ij is the distance between vertices i, j. The derived matrices, to be referred to as restricted random walk matrices and labeled as RRW matrices, are non-symmetric, for trees the entries being of the form 1/p, where p is an integer equal to 1 or larger. In the second part of the report we consider a few invariants of the RRW matrices. We will illustrate the use of one such invariant in a regression analysis. We consider the variations of the entropies in isomeric octanes with skeletal changes. The derived regression, based on a single descriptor, yields the standard error of 1.26 cal K(-1)mol(-1) that is the smallest yet reported in the literature.