Let $L$ be the laplacian matrix of a connected graph $G$ with real positive weights and $N$ vertices, or that can be assumed to have binary weights for simplicity.My goal is to bound $\Vert L^+\Vert_{\infty,\infty}$, where $L^+$ denotes the pseudo-inverse, and $\Vert \cdot\Vert_{\infty,\infty}$ is the maximum absolute value of a matrix entry.
That norm can of course be bounded by the spectral norm of the pseudo-inverse, which is equal to the inverse of the graph's algebraic connectivity (smallest non-null eigenvalue, the Fiedler value).
However, I wonder if it is possible to get a tighter bound.
My attempt is to try to link the pseudo-inverse of $L$ to $L$. If $L$ were invertible, I would have used the identity $"L\operatorname{Adj}(L) = \operatorname{det}(L)I"$ (where $\operatorname{Adj}$ is the adjugate operator), but I couldn't find any analogue formula in the literature. In order to still use the property, I will use the fact that $L^+ = (L + aJ)^{-1}-\frac{1}{a}J$ for any $a>0$ (can be found in https://arxiv.org/pdf/2109.14587.pdf , Lemma 4), where $J = \frac{{\bf 1 1^\top}}{N}$ is the projector onto constant vectors of size $N$, and $\bf 1$ is a vector of ones.
Hence, using the definition of the adjugate matrix one can write: $$\Vert L^+\Vert_{\infty,\infty} \leq \frac{\Vert\operatorname{Adj}(L + aJ)\Vert_{\infty,\infty}}{\operatorname{det}(L + aJ)} + \frac{1}{N}.$$ The determinant of $L+aJ$ is equal to $a N\tau(G)$, where $\tau(G)$ is the number of spanning trees of $G$, as a consequence of Kirchoff's theorem (https://en.wikipedia.org/wiki/Kirchhoff%27s_theorem).
Now, I am left with the norm in the numerator. Since $J$ has rank one, I looked for a rank 1 update formula for the adjugate, aking to the Sherman-Morrison formula(https://en.wikipedia.org/wiki/Sherman%E2%80%93Morrison_formula) or the the determinant lemma (https://en.wikipedia.org/wiki/Matrix_determinant_lemma), but I could not find any.
Hence, I proceeded as follows: $$\Vert\operatorname{Adj}(L + aJ)\Vert_{\infty,\infty} = \max_{i,j}|\operatorname{det}(L_{\setminus ij} + aJ_{\setminus ij})| = \max_{i,j}|\operatorname{det}(L_{\setminus ij}) + a u^\top\operatorname{Adj}(L_{\setminus ij}) u)|$$ Here, $L_{\setminus ij}$ is the submatrix of L obtained by removing row $i$ and column $j$, and $u=\frac{\bf 1_{N-1}}{\sqrt{N-1}}$, and I used the determinant lemma.
From Kirchoff's theorem, we have $|\operatorname{det}(L_{\setminus ij})| = \tau(G)$. Hence, I will only have to deal with the $u^\top\operatorname{Adj}(L_{\setminus ij}) u$ term. The adjugate in this expression entails the computation of second order minors, as first minors of $L_{\setminus ij}$ are second order minors of the Laplacian, i.e. obtained by removing two rows and two columns.
Are there any tips to continue from this position, or for the question in general ?
