The maximum edge derivative conjecture for normalized Laplacian eigenvalues

Let GG be a graph, let x,yx,y be vertices, and let λ\lambda be an eigenvalue of the normalized Laplacian whose edge derivative is being considered. The edge derivative with respect to the pair {x,y}\{x,y\} is denoted by dλd{x,y}\frac{d\lambda}{d\{x,y\}}. Maximum edge derivative conjecture. Over all graphs, the maximum edge derivative for any pair of vertices x,yx,y is 11; i.e.

maxG,{x,y}dλd{x,y}=1.\max_{G,\{x,y\}} \frac{d\lambda}{d\{x,y\}}=1.

The bound is tight for the graph described in the surrounding discussion, and the observed extremal structure involves connected twins. Whether the bound holds for all graphs remains open.

Sources & referencesView supporting material

Primary source

Connor Albright, Kimberly P. Hadaway, Ari Holcombe Pomerance, Joel Jeffries, Kate J. Lorenzen and Abigail K. Nix, “On the Edge Derivative of the Normalized Laplacian with Applications to Kemeny's Constant”, arXiv:2211.01495 (2023).

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.