On walks in molecular graphs

Walks in molecular graphs and their counts for a long time have found appli cations in theoretical chemistry. These are based on the fact that the (i, j)-entry of the kth power of the adjacency matrix is equal to the number of walks starting at vertex i, ending at vertex j, and having length k. In re cent papers (refs 13. 18, 19) the numbers of all walks of length k, called molecular walk counts, mwc(k), and their sum from k = 1 to k = n - 1, calle d total walk count, twc. were proposed as quantities suitable for QSPR stud ies and capable of measuring the complexity of organic molecules. We now es tablish a few general properties of mwc's and twc among which are the linea r dependence between the mwc's and linear correlations between the mwc's an d twc, the spectral decomposition of mwc's, and various connections between the walk counts and the eigenvalues and eigenvectors of the molecular grap h. We also characterize the graphs possessing minimal and maximal walk coun ts.