measure graph complexity Background:
There are 5 ways to represent a mathematical idea: words/text, tables of numbers, plots/figure, symbolic expressions, flowcharts/graph.  
When I ask about "graphs" (below) I do not mean a picture of the relationship of x-vs-y (aka plot), but I do mean the nodes-and-edges, graph-theory version.  I also presume that the graph is connected - there is not any node such that by traversing edges it is impossible to get from that node to any other node in the graph.
Within the words/text there is the idea of cyclomatic complexity for a program.
Within the symbolic expressions we can look at count of operators and count of parameters to get an idea of complexity of an expression.
Question:
What are some ways to measure the complexity of a graph?  Is is an expression comprised of edges and nodes?  Is there a single number?  I would think there are an infinite variety, but I'm not sure how to grapple with this one.  
Example random metric:
How long it takes in step-count, on average, over many trials, with random starting position, for a random graph walker to touch every edge and every node?  Is that a thing?  (I just thought of this, and it is a thing. 1, 2)
Follow-up question:
How does the complexity change for a directional graph, or a directionally weighted graph?  I know that digraphs are a subset of all graphs.  
Update:
Possibly relevant references:


*

*http://www.thi.informatik.uni-frankfurt.de/~jukna/ftp/graph-compl.pdf

*http://www.renyi.hu/~simonyi/grams.pdf
 A: Common graph measures include :


*

*Connectivity : is the graph connected - i.e. can you reach any node from any other node, or can you break the graph down into "islands" or regions that are unreachable from one another?

*Tree-test : does the graph conform to a tree-shape (i.e. can you reach any node from any other node via a single, unique path?) 

*Bipartite Test : some graphs are bipartite, that is, they consist of two groups of nodes, such that members of each group only connect with members of the other group. For example, a graph of buildings and connected utilities (gas, electricity, water) would be bipartite

*Planarity : is the graph planar? That is, can it be drawn on a 2-dimensional surface such that no edges must be drawn intersecting one another?

*Hamiltonian/Eularian tests - can every node in the graph be reached without using the same edge twice? Can a path be traced on the graph such that every edge is visited once, and only once?

*Clique Analysis : what is the maximum clique number of the graph, and how many cliques of each size up to this number exist?

*Center, Diameter, Eccentricity, Periphery, Girth, Expansion and Radius measures : other (non-exhaustive) metrics that describe different aspects of the graph


There's more besides, but here are some links to sites discussing metrics such as these:
https://people.hofstra.edu/geotrans/eng/methods/ch1m3en.html
https://www.nas.ewi.tudelft.nl/people/Piet/papers/TUDreport20111111_MetricList.pdf
https://math.stackexchange.com/questions/301778/what-are-some-measures-of-connectedness-in-graphs
http://www.bu.edu/networks/files/2012/08/basics-of-network-analysis.pdf
And this is a fairly neat list:
http://mathworld.wolfram.com/topics/GraphProperties.html
Another resource is the networkx python library reference:
http://networkx.readthedocs.io/en/stable/reference/index.html
