I made a small package that makes it very easy to call the igraph library through RLink and do graph-computations.  It's not complete, for example it doesn't support edge weights.  You can use this library to verify results returned by Mathematica (which is the main reason why I wrote it).  One problem with graph-related functions is that usually it's more difficult to verify results than in numerical calculations. E.g. an Integrate results can usually be verified using NIntegrate, all within Mathematica.  We can't easily do this for most graph-related functions without resorting to an external library like igraph.

Here's IGraphR.

An an example of its use: