Insensitivity of the minimum eigenvalue under edge addition at the optimal path-graph port

Let nn be odd, and let PnP_n be a path graph with Laplacian matrix LnL_n. For 1-port selection, perturb LnL_n to

L~n=Ln+ϵepepT,\widetilde{L}_n=L_n+\epsilon e_{p^*}e_{p^*}^T,

where p=(n+1)/2p^*=(n+1)/2, and denote the resulting optimal perturbed path graph by PnP_n^*. Form the disjoint union PnPnP_n^*\cup P_n^*, and add one edge between any pair of its nodes such that the resulting graph is connected; denote the resulting connected graph on 2n2n nodes by T2nT_{2n}. Insensitivity conjecture. The minimum eigenvalues satisfy

λmin(Pn)=λmin(PnPn)=λmin(T2n).\lambda_{\min}(P_n^*)=\lambda_{\min}(P_n^*\cup P_n^*)=\lambda_{\min}(T_{2n}).

This conjecture asserts that the minimum eigenvalue is unchanged both by taking two copies of the optimally perturbed path graph and by adding any single edge that makes the union connected. It generalizes the stated result for the path graph to all permitted pairs of nodes for the added edge; its status is unresolved in the supplied source context.

Sources & referencesView supporting material

Primary source

Karim Shahbaz, Madhu N. Belur, Chayan Bhawal and Debasattam Pal, “Optimal k-centers of a graph: a control-theoretic approach”, arXiv:2406.05512 (2024).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.