𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Novel graph distance matrix

✍ Scribed by Milan Randić; Tomaž Pisanski; Marjana Novič; Dejan Plavšić

Publisher
John Wiley and Sons
Year
2010
Tongue
English
Weight
390 KB
Volume
31
Category
Article
ISSN
0192-8651

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

We 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

📜 SIMILAR VOLUMES

On the distance matrix of a directed gra
On the distance matrix of a directed graph
✍ R. L. Graham; A. J. Hoffman; H. Hosoya 📂 Article 📅 1977 🏛 John Wiley and Sons 🌐 English ⚖ 144 KB 👁 2 views

## Abstract In this note, we show how the determinant of the distance matrix __D(G__) of a weighted, directed graph __G__ can be explicitly expressed in terms of the corresponding determinants for the (strong) blocks __G~i~__ of __G__. In particular, when cof __D(G__), the sum of the cofactors of _

Orientation distance graphs
Orientation distance graphs
✍ Gary Chartrand; David Erwin; Michael Raines; Ping Zhang 📂 Article 📅 2001 🏛 John Wiley and Sons 🌐 English ⚖ 194 KB

For two nonisomorphic orientations D and D H of a graph G, the orientation distance d o (D,D H ) between D and D H is the minimum number of arcs of D whose directions must be reversed to produce an orientation isomorphic to D H . The orientation distance graph h o (G) of G has the set y(G) of pairwi

Integral distance graphs
Integral distance graphs
✍ Chen, Jer-Jeong; Chang, Gerard J.; Huang, Kuo-Ching 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 90 KB

Suppose D is a subset of all positive integers. The distance graph G(Z, D) with distance set D is the graph with vertex set Z, and two vertices x and y are adjacent if and only if |x -y| ∈ D. This paper studies the chromatic number χ(Z, D) of G(Z, D). In particular, we prove that χ(Z, D) ≤ |D| + 1 w

Distance-regular Subgraphs in a Distance
Distance-regular Subgraphs in a Distance-regular Graph, III
✍ Akira Hiraki 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 254 KB

Let ⌫ be a distance-regular graph with l (1 , a 1 , b 1 ) ϭ 1 and c s ϩ 1 ϭ 1 for some positive integer s . We show the existence of a certain distance-regular graph of diameter s , containing given two vertices at distance s , as a subgraph in ⌫ .