Minimum spectral radius of a weighted graph (Q1188417)

A basic graph \(G_ 0\) is a graph with components \(C_ 1,\dots,C_ k\) (odd cycles) and \((A_ 1,B_ 1),\dots,(A_ s,B_ s)\) (balanced bipartite graphs). Define \[ R(G_ 0)={1\over 2}\sum^ k_{i=1}| C_ i|+\sum^ s_{i=1}\sqrt{| A_ i| | B_ i|}. \] Let \(G\) be a graph. Define \(R(G)=\max R(G_ 0)\), where the maximum is taken over all basic subgraphs \(G_ 0\) of \(G\). In this paper, the author found a polynomial algorithm to find a basic subgraph \(G_ 0\) of a graph \(G\) with \(R(G_ 0)\) maximum. This algorithm can be applied to determine the optimal distribution of nonnegative weights (with total sum one) among the edges of a given graph, so that the spectral radius of the resulting adjacency matrix is minimum.