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.

Improve this question
$\endgroup$
2
  • 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
    Commented Feb 21, 2014 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
    Commented Feb 21, 2014 at 13:37

1 Answer 1

Reset to default
3
$\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.

Improve this answer
$\endgroup$
1
  • 4
    $\begingroup$ I know this one under the name Hofmeister's bound. $\endgroup$
    – Felix Goldberg
    Commented Feb 21, 2014 at 17:58

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .