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= Σ min( degu,degv ) (u,v)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 105 , 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 105.

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

O(mm)

  • »
    »
    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 >=m. Maximum size of this set will be m

    2) With degree <=m

    Sum of contributions of all edges where at least one endpoint lies in second set will be at max mm

    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 (deg[u]bdeg[u]) since bdeg[u]<=m, contribution becomes (deg[u]m), if we pull the m outside the summation then m(deg[u])<=mm