Note on von Neumann and R\'enyi entropies of a Graph
  We conjecture that all connected graphs of order $n$ have von Neumann entropy at least as great as the star $K_{1,n-1}$ and prove this for almost all graphs of order $n$. We show that connected graphs of order $n$ have R\'enyi 2-entropy at least as great as $K_{1,n-1}$ and for $\alpha>1$, $K_n$ maximizes R\'enyi $\alpha$-entropy over graphs of order $n$. We show that adding an edge to a graph can lower its von Neumann entropy. 
Michael Dairyko, Leslie Hogben, Jephian C.-H. Lin, Joshua Lockhart,   David Roberson, Simone Severini, Michael Young
math.CO quant-ph