Simple expressions for the long walk distance

DOI10.1016/J.LAA.2012.07.033MaRDI QIDQ389550zbMATH OpenOpenAlexFDO

Authors Pavel Chebotarev, R. B. Bapat, R. Balaji

Publication date 21 January 2014

Published in Linear Algebra and its Applications (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1112.0088

zbMATH Keywords

g-inversegraph distancesgraph-geodetic distancelong walk distancepara-Laplacian matrixresistance distancesingular M-matrixwalk distances

Mathematics Subject Classification ID

Distance in graphs (05C12) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Positive matrices and their generalizations; cones of matrices (15B48)

Abstract: The walk distances in graphs are defined as the result of appropriate transformations of the $su{m}_{k=0}^{i}nfty(tA{)}^k$ proximity measures, where $A$ is the weighted adjacency matrix of a connected weighted graph and $t$ is a sufficiently small positive parameter. The walk distances are graph-geodetic, moreover, they converge to the shortest path distance and to the so-called long walk distance as the parameter $t$ approaches its limiting values. In this paper, simple expressions for the long walk distance are obtained. They involve the generalized inverse, minors, and inverses of submatrices of the symmetric irreducible singular M-matrix $calL=hoI-A,$ where $ho$ is the Perron root of $A.$

Recommendations

• The walk distances in graphs
• A topological interpretation of the walk distances
• Expected distance based on random walks
• A class of graph-geodetic distances generalizing the shortest-path and the resistance distances
• Proximity, remoteness and distance eigenvalues of a graph

Cites work

• A class of graph-geodetic distances generalizing the shortest-path and the resistance distances
• A new status index derived from sociometric analysis
• scientific article; zbMATH DE number 5784227 (Why is no real title available?)
• scientific article; zbMATH DE number 1460605 (Why is no real title available?)
• scientific article; zbMATH DE number 3290993 (Why is no real title available?)
• scientific article; zbMATH DE number 3373921 (Why is no real title available?)
• Identities for minors of the Laplacian, resistance and distance matrices
• Inequalities and equalities associated with the Campbell-Youla generalized inverse of the indefinite admittance matrix of resistive networks
• Limits and the Index of a Square Matrix
• The graph bottleneck identity
• The walk distances in graphs

Cited in

(2)

• A topological interpretation of the walk distances
• The walk distances in graphs

This page was built for publication: Simple expressions for the long walk distance

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q389550)