AbstractWe have introduced novel distance matrix for graphs, which is based on interpretation of columns of the adjacency matrix of a graph as a set of points in n‐dimensional space, n being the number of vertices in the graph. Numerical values for the distances are based on the Euclidean distance between n points in n‐dimensional space. In this way, we have combined the traditional representation of graphs (drawn as 2D object of no fixed geometry) with their representation in n‐dimensional space, defined by a set of n‐points that lead to a representation of definite geometry. The novel distance matrix, referred to as natural distance matrix, shows some structural properties and offers novel graph invariants as molecular descriptors for structure‐property‐activity studies. One of the novel graph descriptors is the modified connectivity index in which the bond contribution for (m, n) bond‐type is given by 1/√(m + n), where m and n are the valence of the end vertices of the bond. The novel distance matrix (ND) can be reduced to sparse distance‐adjacency matrix (DA), which can be viewed as specially weighted adjacency matrix of a graph. The quotient of the leading eigenvalues of novel distance‐adjacency matrix and novel distance matrix, as illustrated on a collection of graphs of chemical interest, show parallelism with a simple measure of graph density, based on the quotient of the number of edges in a graph and the maximal possible number of edges for graphs of the same size. © 2010 Wiley Periodicals, Inc. J Comput Chem, 2010