I have connected graphs, each with the same N vertices. Each graph contains edges connecting the vertices to their nearest neighbor, as determined by a distance function. A different distance function is used for each graph, and as such the edges vary a little or a lot from graph to graph.
Searching the literature, I've found a few measures of comparison e.g. Zagreb, % edge overlap.
How would a graph theorist compare these graphs, especially by scalar measures? Perhaps there is a review of the literature paper?
Here's an example graph: http://figdb.org/2010_Ficus_SSR_DFIC_Theta_layered_graph.jpg
