Consider a connected graph of N nodes.
Assign randomly to each node a distinct number from 1 to N.
For each node consider the maximum adjacent value or itself if all adjacent values are smaller.
Define the set that contains these distinct values.
Can you deliver an upper bound for the expected value of the cardinality of this set like c*N for any connected graph of N nodes?
[Math] Expected Value for a Connected Graph
graph theoryrandom-graphs
Best Answer
To obtain some linear bound you need just to assume that each vertex has degree at least one.
Say that the vertex contains tthe number $a_i$, and its maximum is $b_i$. The probability that $b_i\leq N/2$ is less than $1/4$ (in fact, it is less that $1/2^{d+1}$ where $d$ is the degree of the $i$th vertex). Thus the expected number of vertices with $b_i\leq N/2$ is less than $N/4$, and, a fortiori, the expected number of such values is less than $N/4$. Therefore, the expected number of distinct values is at most $3N/4$.
(We need to be a bit more careful with odd $N$, but at least the asymptotics is clear.)
Surely this estimate is quite rough.