Boost Graph Library and LEMON
As Daniel mentions in his comprehensive answer, the most full-featured general C++ library is the Boost Graph Library. There is a new distributed-memory extension capable of doing some basic algorithms such as breadth-first and depth-first search, minimum spanning trees, and connected components search, but I am not very familiar with the new project. The Boost Graph Library itself is well-reputed and used in many projects around the world.
If you are doing basic HPC graph work, you might want to start with the Boost Graph Library, but be aware that many HPC C++ compilers have difficulty with Boost (despite its fairly strict adherence to C++ standards), and you may need to use an older version of Boost or a non-vendor compiler such as GCC to get it working on HPC systems.
A quick browse of LEMON's repositories shows that there is involvement from the IBM BlueGene supercomputing team, but I don't see any dependencies or configuration for MPI, so this is likely to only be a serial graph library at the moment.
Load-balancing and Dynamic graph (re)-partitioning
If you are interested in load-balancing and dynamic graph partitioning, you have several more options. Perhaps the most well-known library is ParMETIS, which was updated to version 4 last year. ParMETIS features vertex-based weighting, which is important for multi-physics simulations.
ParMETIS's European competitor is PT-Scotch, which has had better performance for certain types of problems, but, similar to ParMETIS, is not frequently updated.
You may also be interested in Zoltan, which is part of the Sandia National Laboratories Trilinos meta-package for scientific computing in C++. Zoltan features its own hierarchical partitioners and interfaces into both ParMETIS and PT-Scotch.
If you are working on the bleeding edge of concurrent search, optimization (single source shortest path), and edge-oriented (maximal independent set), you will also be interested in the freely available Graph500 benchmark.