What is a graph defined by a recurrence relation called

Question

Say I have a set of graphs $\mathcal{G}$ defined by a base graph $G_0=(V_0, E_0)$ and a recurrence relation $f:G_i\mapsto G_{i+1}$. Does such a graph or set of graphs have a name? If not, is there a term from set/group theory or abstract algebra that is appropriate?

Answer 1

I would just call such objects a recursive sequence of graphs.

There are several places in graph theory where graph sequences come up, and I've never encountered any special terminology for them:

• I've already mentioned the iterated Mycielskian construction in a comment.
• One might construct a sequence of good expander graphs iteratively using the zig-zag product, though there we're not too interested in the sequence itself, just that there exist arbitrarily large graphs with this property.
• In the study of graph limits, we discuss convergent graph sequences (sequences of graphs $(G_n)$ such that the density of any fixed induced subgraph $H$ has a limit as $n \to \infty$).

Often people do talk about "families" of graphs rather than "sequences" of graphs, even if the graphs are explicitly indexed by the natural numbers. For example, see Lévy families. So I wouldn't be too surprised to see the objects you're talking about called something like an "iteratively constructed family of graphs", too.