A note on doubly stochastic graph matrices (Q2568396): Difference between revisions

Let \(G\) be a tree with vertex set \(V(G):=\{v_1,\dots, v_n\}\) and edge set \(E(G)\). Let \(d_i\) be the degree of \(v_i\), \(D(G)= \operatorname{diag}(d_1,\dots, d_n)\), \(A(G)\) the adjacency matrix of \(G\), \(L(G):=D(G)-A(G)\), the Laplacian matrix of \(G\). It is well known that the matrix \(\Omega(G):=(I_n+L(G))^{-1}\) is a doubly stochastic matrix. \textit{R. Merris} [Linear Multilinear Algebra 45, 275--285 (1998; Zbl 0944.05065)] posed the following question: does there exist a constant \(c\), independent of \(n\), such that \(\Omega(G)_{ij}\geq \frac cn\) whenever \(L(G)_{ij}=1\)? This note provides a negative answer to this problem: \(\omega(G)_{ij}\geq \frac 4{([\frac n2]+3)^2-4}\) for those \(L(G)_{ij}=1\); and the equality in the inequality holds if and only if \(G\) is a double star tree \(T^*_{[\frac n2]-1, [\frac n2]-1}\).