Graph Weight Allocation to Meet Laplacian Spectral Constraints

We adjust the node and edge weightings of graphs using convex optimization to impose bounds on their Laplacian spectra. First, we derive necessary and sufficient conditions that characterize the feasibility of spectral bounds given positive node and edge weightings. Synthesizing these conditions leads naturally to algorithms that exploit convexity to achieve several eigenvalue bounds simultaneously. The algorithms we propose apply to many graph design problems as well as multi-agent systems control. Finally, we suggest efficient ways to accommodate larger graphs, and show that dual formulations lead to substantial improvement in the size of graphs that can be addressed.