There seem to be many very interesting problems in graph theory that can be written in the form of maximizing/minimizing a quadratic form on either the Adjacency ${\bf A}$ or the Laplacian matrix ${\bf L}$ of a graph. Examples are: 1) the max-cut problem is equivalent to finding a sign vector that maximizes a quadratic form$$\max_{x_i\in\{\pm1\}} \sum_{i,j}A_{i,j}(1- x_ix_j),$$2) The densest $k$-subgraph is equivalent to$$\max_{x_i\in\{0,1/\sqrt{k}\},\;{\bf 1}^T{\bf x}=1} {\bf x}^T{\bf A}{\bf x}$$3) The Grothendieck constant involves maximizing the adjacency's quadratic form over sign vectors$$\max_{x_i\in\{\pm1\}} {\bf x}^T{\bf A}{\bf x},$$4) The spectral profile of a graph $$\Lambda(\delta) = \min_{d(\text{supp}({\bf x}))\le \delta} \frac{{\bf x}^T{\bf L}{\bf x}}{\sum_i \text{deg}(\text{vertex}_i) x_i^2},$$where $d(\text{supp}(x))$ is the fraction of edges incident on vertices within the support of vector ${\bf x}$( http://www.eecs.berkeley.edu/~prasad/Files/spectralprofile.pdf )4+$\epsilon$) Anything involving the computation of an adjacency/laplacian eigenvalue.${\bf Q}$: Which other problems in graph theory can be expressed as maximizing/minimizing a quadratic form?
Which problems in graph theory can be stated as quadratic programs?
graph theory;optimization;spectral graph theory