I can't imaging anything graph specific, so I would chose the standard ROS tools. For a constant entity the parameter server seems fitting. You could define the adjacency for each node as a list. In all cases this will require a node list that can be indexed.
For anything more advanced a custom message might be better. This can be saved and replayed on a latched topic.
If the graph is not too big, you might want to use a bagy (i.e. rostopic echo output) so that the matrix is human readable/editable.
The advantage of a message would be that it is probably easier to add custom values to nodes and edges (like covariances, costs, etc.).
If the matrix is quite full and large, you might just want to define the adjacency matrix (e.g. as row-first indices), like so:
Node[] nodes
uint32 adjacency
For sparse or smaller matrices a separate Edge definition seems easier:
Node[] nodes
Edge[] edges
Edge.msg
uint32 from
uint32 to
other stuff...
Is that constant throughout a run or does it change over time?
For the moment it's a connection graph, so constant. But out of curiosity I'd like to hear of possible solutions for time-varying matrices too.
Christian please allow me to bring your attention back to this question, I'd really like any kind of pointer or idea.