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.