The 2 papers below give the expected efficiency of the method of simply running a random walk on your graph, until the $n$ nodes are covered, between $n\ln n$ steps on a nice graph like the complete one, and $\tfrac4{27}n^3$ steps on the lollipop graph, cf.:

• U. Feige, A tight upper bound on the cover time for random walks on graphs, Random Struct Alg 6(1) (1995), 51-54.

• U. Feige, A tight lower bound on the cover time for random walks on graphs, Random Struct Alg 6(4) (1995), 433-438.

The 2 papers below show that the expected efficiency of the method of simply running a random walk on your graph, until the $n$ nodes are covered, ranges from $n\ln n$ steps on a nice graph like the complete one, to $\tfrac4{27}n^3$ steps on the lollipop graph, cf.:

• U. Feige, A tight upper bound on the cover time for random walks on graphs, Random Struct Alg 6(1) (1995), 51-54.

• U. Feige, A tight lower bound on the cover time for random walks on graphs, Random Struct Alg 6(4) (1995), 433-438.

The 2 papers below give the expected efficiency of the method of simply running a random walk on your graph, until all the nodes are covered, between $n\ln n$ steps on a nice graph like the complete one, and $\tfrac4{27}n^3$ steps on the lollipop graph, cf.:

• U. Feige, A tight upper bound on the cover time for random walks on graphs, Random Struct Alg 6(1) (1995), 51-54.

• U. Feige, A tight lower bound on the cover time for random walks on graphs, Random Struct Alg 6(4) (1995), 433-438.

The 2 papers below give the expected efficiency of the method of simply running a random walk on your graph, until the $n$ nodes are covered, between $n\ln n$ steps on a nice graph like the complete one, and $\tfrac4{27}n^3$ steps on the lollipop graph, cf.:

• U. Feige, A tight upper bound on the cover time for random walks on graphs, Random Struct Alg 6(1) (1995), 51-54.

• U. Feige, A tight lower bound on the cover time for random walks on graphs, Random Struct Alg 6(4) (1995), 433-438.