6
$\begingroup$

Let $G$ be a graph with degrees $d_{1},\ldots,d_{n}$. I am interested in upper bounds on $$ \sum_{i=1}^{n}{d_{i}^{2}}. $$ An example is de Caen's bound: $$ \sum_{i=1}^{n}{d_{i}^{2}} \leq e(\frac{2e}{n-1}+n-2), $$ where $e$ is the number of edges. His bound is very elegant but far from tight. I have read many papers which give other bounds but now I am a bit confused and would love to know if someone can supply a definitive answer.

P.S. The quantity in question is also known as the "first Zagreb index", mostly in chemistry-related circles.

$\endgroup$
  • 3
    $\begingroup$ This was address in the TCS question, "Bounds on sum of squares of node degrees in undirected graphs," where David Eppstein's answer may be of some help. $\endgroup$ – Joseph O'Rourke Feb 21 '14 at 13:16
  • 2
    $\begingroup$ A quick search yields the paper New sharp bounds on the first Zagreb index, where they show that for connected graphs $G=(V,E)$, $$M_1(G) \leq e(e+1)$$ $$M_1(G) \leq n(2n-e+1)$$which are each sharp for some graphs. Cauchy-Schwarz yields the lower bound $$4e^2/n\leq M_1(G).$$ We are essentially trying to bound the second moment of a function $d:V\rightarrow \mathbb{N}$ by the first moment and the size of the domain $V$, so any simple bounds will not be tight in every case. $\endgroup$ – Eric Naslund Feb 21 '14 at 13:37
4
$\begingroup$

There is a simple spectral upper bound: namely, denoting by $A$ the adjacency matrix of $G$, and by $\mathbf 1$ the $n$-dimensional all-$1$ vector, we have $$ \sum_{I=1}^n d_i^2=\|A{\mathbf 1}\|^2 \le \|A\|^2 \|{\mathbf 1}\|^2 = n\lambda_{\rm max}^2, $$ where $\lambda_{\rm max}$ is the largest eigenvalue of $G$. This bound is sharp, say, for regular graphs.

$\endgroup$
  • 4
    $\begingroup$ I know this one under the name Hofmeister's bound. $\endgroup$ – Felix Goldberg Feb 21 '14 at 17:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.