Perhaps you could attach the code of a minimal working example?

of course, i can give you a link to the example i've tested [0] and here below is the graph i used (METIS):

5 9 1
3 1
2 2 4 1 5 2
2 7 4 3
5 1
1 1 2 1

[0] http://www.boost.org/doc/libs/1_44_0/libs/graph_parallel/example/breadth_first_search.cpp

To compile the example you have to link:

boost_graph_parallel-mt
boost_mpi-mt
boost_system-mt

Thanks for your time.

--
Best regards,
Mattia