aknov711's blog

By aknov711, history, 2 years ago, In English

Recently, I got stuck in this line of thoughts.. Given a graph with n nodes and m edges with no cycles and multiple edges. Consider the summation of minimum degrees of the two endpoints of every edge of the graph.

More formally, wann'a know bound for

S= $$$\Sigma$$$ min( $$$deg_u,deg_v$$$ ) $$$\forall (u,v) \in E$$$

What would it be assympotically equal to ? Definitely, one upperbound can be O(n*m) since the largest degree for any node can ne n-1.

Suppose if n and m both are of order $$$10^5$$$ , then what it would be equal to? Can you share your thoughts on this ?

  • Vote: I like it
  • +8
  • Vote: I do not like it

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

No cycles? So you mean the graph is a forest and m <= n-1 ? Please correct me if I'm wrong.

  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    O sorry, my bad. It may conatin cycles. The main point is that the number of edges is bounded by $$$10^5$$$.

»
2 years ago, # |
  Vote: I like it +3 Vote: I do not like it

$$$O(m*\sqrt m)$$$

  • »
    »
    2 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    which is achieved in a complete graph, but I think op is more interested in the proof

  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yeh, I too thought of it, but didn't got any proof for it. Can you please share how can it be so?

  • »
    »
    2 years ago, # ^ |
    Rev. 2   Vote: I like it +32 Vote: I do not like it

    Separate vertices in to two sets

    1) With degree $$$>=\sqrt m$$$. Maximum size of this set will be $$$\sqrt m$$$

    2) With degree $$$<=\sqrt m$$$

    Sum of contributions of all edges where at least one endpoint lies in second set will be at max $$$m*\sqrt m$$$

    Now let's assume for any vertex 'u' in first set, $$$bdeg[u]$$$ is no of adjacent vertices that are also in first set.

    Then contribution is $$$\sum{(deg[u]*bdeg[u])}$$$ since $$$bdeg[u]<=\sqrt m$$$, contribution becomes $$$\sum{(deg[u]*\sqrt m)}$$$, if we pull the $$$\sqrt m$$$ outside the summation then $$$\sqrt{m}*\sum(deg[u]) <= \sqrt{m}*m$$$