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$?

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$.

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

$$\max_{f:V\rightarrow [\frac{-1}{2},\frac{1}{2}], \\ \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$?

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

Is this parameter polynomially computable?

Remark: Note that we have $$\max_{f:V\rightarrow [\frac{-1}{2},\frac{1}{2}], \\ \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$.

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$.

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$?

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$.

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

$$\max_{f:V\rightarrow \mathbb R, \\ f\text{ is non-constant}} \frac{f^T L_G f}{n-f^Tf} ,$$

where $L_G=D_G-A_G$ is the laplacian matrix of $G$?

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, \\ f\text{ is non-constant}} \frac{f^T L_G f}{f^Tf} = \lambda_n(G),$$ where $\lambda_n(G)$ is the largest eigenvalue of $L_G$.

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$.