R. Merris, Doubly stochastic graph matrices, ii, Linear & Multilinear Algebra 45 (1998), 275-285. Math Reviews 99k:05110.

This article is a continuation of publication 100: Denote by L(G) the Laplacian matrix of the n-vertex graph G. Let omega(G) be the smallest element in the doubly stochastic matrix Omega(G) = inv[I + L(G)]. Then, e.g., omega(G) > 0 with equality if and only if G is disconnected, and omega(G) < 1/(n+1) with equality if and only if G is the complete graph on n vertices. If i is different from j, the (i,i)-entry of Omega(G) is not less than twice its (i,j)-entry, with equality if and only if the ith vertex of G is adjacent to every other vertex.

There is a misprint in Conjecture 2. It should read: If n > 3, then omega(En) = 1/[2(n+1)]. Conjecture 2 is now a theorem, proved by A. Berman and X.-D. Zhang, A note on degree antiregular graphs, Linear & Multilinear Algebra 47 (2000), 307-311.

A counterexample to Conjecture 1, that the algebraic connectivity of G is bounded below by 2(n+1)omega(G), was communicated to the author by Jia-Xi Wu in mid July, 2003.

Among the articles citing this paper are