Graphs with Large Variance

For a graph \(G\), let \(Var(G)\) denote the variance of the degree sequence of \(G\), let \(sq(G)\) denote the sum of the squares of the degrees of \(G\), and let \(t(G)\) denote the number of triangles in \(G\) and in its complement. The parameters are related by:
\(Var(G) = \frac{sq(G)}{n} – d^2\)
where \(d\) is the average degree of \(G\), and
\(t(G) = \binom{n}{3} + \frac{sq(G)}{2} – {m(n-1)}\)
Let \(Var(n)\) denote the maximum possible value of \(Var(G)\) where \(G\) has \(n\) vertices, and let \(sq(n,m)\) and \(t(n,m)\) denote the maximum possible values of \(sq(G)\) and \(t(G)\), respectively, where \(G\) has \(n\) vertices and \(m\) edges. We present a polynomial time algorithm which generates all the graphs with \(n\) vertices and \(m\) edges having \(sq(G) = sq(n,m)\) and \(t(G) = t(n,m)\). This extends a result of Olpp which determined \(t(n,m)\). We also determine \(Var(n)\) precisely for every \(n\), and show that
\[ Var(n) = \frac{q(q-1)^2}{n}(1-\frac{q}{n}) =\frac{27}{256}n^2=O(n)\]
where \(q = [\frac{3n}{4}] \),(if \(n \equiv 2 \pmod 4\) the rounding is up ) thereby improving upon previous results.