Let $G=(V,E)$ be a simple undirected graph on $n$ nodes, with node weights $W = [w_1,w_2,\dots,w_n] \in \mathbb{R}^n$. Define the weight for a sequence of nodes $v_1,v_2,\dots,v_k$ by the average $\frac{1}{k}\sum_{i=1}^k w_i$. Given $k$, find the tightest possible upper bound on the maximum average weight.

Consecutive vertices in the sequence are not constrained to be connected by an edge, and the vertices in the sequence do not have to be distinct. Instead, the sequence is required to satisfy the following property:

  • A vertex $v_i$ can only be appended to the end of the sequence if at least one of its neighbours has been added since the last occurence of $v_i$ (with the exception that a vertex that has never occurred in the sequence can be added at any time).
  • $\begingroup$ I take it from your final sentence that the $k$ vertices need not be distinct? And in your average formula, do you want $w_i$ in the summand rather than $v_i$? $\endgroup$ – Vidit Nanda Aug 1 '13 at 3:05
  • $\begingroup$ Good point, question updated! $\endgroup$ – Mark Schmidt Aug 1 '13 at 4:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.