Skip to main content
3 of 5
added 11 characters in body
j.s.
  • 705
  • 4
  • 12

Is the value of $\max_{x} \frac{x^T L_G x}{n-x^Tx}$ polynomially computable?

For a graph $G$ on $n$ vertices, what is the value of following ratio:

$$\max_{f:V\rightarrow \mathbb R, \\ \sum_{v}{f(v)}=0} \frac{f^T L_G f}{n-f^Tf} ,$$

where $L_G=D_G-A_G$ is the laplacian matrix of $G$, and $1$ is all-one vector?

Is this parameter related to the spectrum of $G$?

Is this parameter polynomially computable?

Remark: Note that we have $$\max_{f:V\rightarrow \mathbb R, \\ \sum_{v}{f(v)}=0} \frac{f^T L_G f}{f^Tf} = \lambda_n(G),$$ where $\lambda_n(G)$ is the largest eigenvalue of $L_G$.

j.s.
  • 705
  • 4
  • 12