Measuring Memorability of Graphs

Psychologists study aspects of how human memory works. One fellow I talked to 
is interested in how well people can memorize graph structures, and needed a 
measure of how "difficult" a graph structure would be to memorize. There are a 
zillion different graph invariants one encounters in the graph theory literature, 
but is there one which corresponds to a notion of memorability, or entropy, or structure.

We discussed a variety of possibilities. Most interesting were notions related to 
finding the smallest number of highly-structured subgraphs (e.g. cliques, stars) 
whose union makes up the graph. These problems tend to be well-known hard problems.  
For example, covering a graph with the minimum number of stars is exactly the vertex 
cover problem.