R. Merris, Doubly stochastic graph matrices, Univ. Beograd. Publ. Elektrotehn. Fak. 8 (1997), 64-71. Math Reviews 98h:15042.

If G is a graph on n vertices, its Laplacian matrix L(G) = D(G) - A(G) is the difference of the diagonal matrix of vertex degrees and the adjacency matrix. It is well known that L(G) is positive semidefinite and singular. This article explores "Omega(G)", the inverse of I + L(G). It turns out that Omega(G) is a positive definite doubly stochastic matrix that is entrywise positive if and only if G is connected. Results in this article overlap [Pavel Yu. Chebotarev and Elena Shamis, On the proximity measure for graph vertices provided by the inverse Laplacian characteristic matrix, Abstract, 5th ILAS Conference, Atlanta, 1995].

The article is cited in

  • P. Yu. Chebotarev and E. V. Shamis, Automation and Remote Control 58 (1997), 1505-1514.
  • P. Yu. Chebotarev and E. V. Shamis, Automation and Remote Control 59 (1998), 608-612.
  • P. Yu. Chebotarev and E. V. Shamis, Automation and Remote Control 59 (1998), 1443-1459.
  • A. Berman and X.-D. Zhang, Linear & Multilinear Algebra 47 (2000), 307-311.
  • P. Yu. Chebotarev and E. V. Shamis, Automation and Remote Control 61 (2000), 1364-1373.
  • S. J. Kirkland, J. J. Molitierno, and M. Neumann, Linear & Multilinear Algebra 48 (2001), 237-246.
  • R. P. Agaev and P. Yu. Chebotarev, Automation and Remote Control 62 (2001), 443-466.
  • P. Chebotarev and R. Agaev, Linear Algebra Appl. 356 (2002), 253-274.

    • It is shown in the sequel that the smallest element of Omega(G) can actually decrease when the graph is perturbed by the addition of a new edge.

    It is an open problem whether for "almost all" trees T there exists a nonisomorphic tree T' such that Omega(T) and Omega(T') are "coimmanantal" in the sense of publication 90.