Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

By Cauchy-Schwartz and the handshake lemma, it is easy to see that $\left( \sum_{i=1}^n \sqrt d_i \right)^2 \leq n \sum_{i=1}^n d_i =2mn$, with equality iff the graph is regular (constant degree). Here $d_i$ is the degree of vertex $i$, $m$ is the number of edges and $n$ is the number of vertices.

Is there a good lower bound for a simple connected graph? I wonder if the lower bound might be half the upper bound?

share|improve this question
add comment

3 Answers

up vote 7 down vote accepted

Given a fixed number of edges and vertices, Linial and Rozenman conjectured that the graphs which minimize $\sum_i \sqrt{d_i}$ are the ones given by taking the largest possible complete graph together with an extra vertex of remaining degree and the rest as isolated vertices. Their conjecture was proved in "Minimizer graphs for a class of extremal problems" by Dan Ismailescu and Dan Stefanica, Journal of Graph Theory (39), 230–240, 2002.

Since you are interested in connected graphs, perhaps that is of little use to you. I will mention one more paper which gives a lower bound on $\sum_i \sqrt{d_i}$. See "Sums of powers of the degrees of a graph" by S. M. Cioabă (Theorem 8), which gives a lower bound in terms of the number of vertices, edges, and minimum and maximum degree.

Finally there is also the amusing lower bound by Székely, Clark and Entriger $$\left(\sum_{i=1}^n \sqrt{d_i}\right)^2\geq \sum_{i=1}^n d_i^2.$$

share|improve this answer
    
Thanks Gjergji, that's very helpful! Still I wonder if $\left( \sum_{i=1}^n \sqrt d_i \right)^2 \geq kmn$ for some $k$ for all connected simple graphs? Note that for a star graph, which we might suspect is extreme, $k=1$ works. –  user31016 Jun 10 '13 at 16:19
add comment

As I did not check the details, please note that this answer is provided with no warranty; use it at your own risks.

If you study the functional $F(d_1,\dots,d_n)$ over the domain defined by $\sum d_i=2m$ and $d_i\geq 1$, you should find that the only critical point is the one that gives your upper bound (which, by the way, is a sibling of the arithmetico-geometric inequality and a consequence of concavity of $\sqrt{\cdot}$ : one is comparing the arithmetic mean with its $\sqrt{\cdot}$-conjugate). It follows that any minimum of $F$ must be localized on the boundary, and by symmetry we can assume $d_n=1$. Then optimizing in $d_1,\dots,d_{n-1}$ is the same game, so you should find that the minimum is obtained precisely when all but one of the $d_i$ are $1$, and the remaining one is $2m-n+1$, giving $$\sum_1^n \sqrt{d_i} \geq \sqrt{2m-n+1}+n-1$$ and this must be achieved by any star-graph.

Note that in terms of $n$ alone, as connectedness implies $m\geq n-1$ you get $$\sum_1^n \sqrt{d_i} \geq \sqrt{n-1}+n-1$$ (again achieved by a start graph).

share|improve this answer
add comment

Benoît:

  • isn't the polytope you are optimizing over a bit more complicated, what about the constraint $d_i \leq n-1$, which will imply boundary constraints with $d_i = n-1$?

  • not every point satisfying your inequality constraints will be the degree sequence of a (connected, simple) graph.

  • your first construction will break if $2m-n+1 > n-1$, i.e. if $m > n-1$. Since the graph is assumed to be connected, this means your first construction breaks for all graphs which are not trees.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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