Consider the set $S$ of multigraphs defined recursively as follows:
Example Graph Class
A graph $G$ is in $S$ if(f)
- $G$ is a loop on a single vertex, or
$G$ may be obtained by selecting a graph $G'\in S$ and applying one of the following operations:
- Add an edge between two extant vertices, or
- Split an edge (add a vertex halfway along an edge) and add an edge between the newly created vertex and any vertex.
I am studying a number of recursively constructed graph classes similar to this example. In particular, for each of these classes I would like to count the number of unlabeled graphs that can be produced after $n$ applications of a set of graph operations similar to the above.
Continuing our example, the graphs counted for $n=1,2,$ and $3$ are pictured here:
Are there are any general combinatorial techniques used to count graphs in this setting?
Regardless of the existence of general techniques, how might you go about counting my example above?
I am aware of the Polya enumeration theorem, but was unsure if the extra recursive information might be better leveraged with some other technique, or whether this particular statistic would make it difficult to apply Polya's theorem. Importantly, whether or not a graph is counted for a particular $n$ is not directly related to neither the number of vertices nor the number of edges in the graph.