Is there any stricter upperbound of this ?

Правка en1, от aknov711, 2022-09-01 13:46:18

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 ?

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en1 Английский aknov711 2022-09-01 13:46:18 613 Initial revision (published)