I’m interested in the minimum number of edges required to specify a graph $G$ uniquely when $G$ is known to satisfy some property.
For example, if we know that $G$ is a cycle graph on $n > 3$ vertices, we need to specify at least $n-2$ edges to fully determine $G$. That is, if we are given $n-2$ edges $(2,3), (3,4),\ldots, (n-1,n)$ then the only way $G$ is a cycle graph is if we also have the edges $(1,2)$ and $(n,1)$. Note that ‘up to isomorphism’ is not sufficient, the vertices of $G$ are labelled so we want to recover it exactly.
Another example could be: if $G$ is a tree on $n$ vertices such that every vertex has degree at most 3, what is the minimum number of edges one needs to specify to uniquely identify $G$?
Have such problems been studied before? I assume this could have something to do with efficient storage of graphs, although I’m not really sure where to look.