1
$\begingroup$

This is not homework. I was asked about the following problem by a friend.

Given a graph with $n$ nodes, initially with only one while node and all the rest are black. Each round, nodes are paired in two, and if any one of them is white, then both of them will become (or remain) white. So on average, how many rounds are needed for all the nodes to become white uniformly?

Please help me. Thank you.

  • 0
    @MarkDominus: right, that is very good heuristics. But how to make it formal proof?2012-05-28

1 Answers 1

2

This is a case of Randomized Rumor Spreading. Normally, one uses one of the following three models for rumor spreading in graphs:

Push model: In each round, every white vertex calls an adjacent vertex, and colors them white.

Pull model: In each round, every black vertex calls an adjacent vertex, and if they call a white vertex, they become white themselves.

Push/Pull model: In each round, both of the above happen.

When you consider different random graph models, such as the Erdős–Rényi Model, or the Preferential Attachment model, you can get bounds of $\log n$ or better. This also holds for complete graphs.

Actually, there would be cases for your model where the vertices do not become white. Consider for example a path on 4 vertices, where the end vertex is white. In each round, you pick a perfect matching, and there is only one of those. In this case, the other end of the path will never become white.

  • 1
    That can be found here: http://www.maths.bris.ac.uk/~maajg/teaching/complexnets/rumours.pdf2012-05-28