We study a new optimal stopping problem: Let $G$ be a fixed graph with $n$ vertices which become active on-line in time, one by another, in a random order. The active part of $G$ is the subgraph induced by the active vertices. Find a stopping algorithm that maximizes the expected number of connected components of the active part of $G$. We prove that if $G$ is a $k$-tree, then there is no asymptotically better algorithm than `wait until $\frac{ 1}{ k+1}$ fraction of vertices'. The maximum expected number of connected components equals to $$\left(\frac{ k^k}{ (k+1)^{ k+1}}+o(1)\right)n.$$
Categories: math.CO math.PR