Timeline for What is/are the best bound/s on the sum of squares of degrees in a graph?
Current License: CC BY-SA 3.0
4 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Feb 21, 2014 at 16:47 | answer | added | Seva | timeline score: 3 | |
| Feb 21, 2014 at 13:37 | comment | added | Eric Naslund | 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. | |
| Feb 21, 2014 at 13:16 | comment | added | Joseph O'Rourke | 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. | |
| Feb 21, 2014 at 13:02 | history | asked | Felix Goldberg | CC BY-SA 3.0 |