techniques or examples of analyzing a series of graphs

Question

Let there be a sequence of graphs $G_1, G_2, G_3, ...$ constructed using some particular approach or algorithm. in this particular case $G_n$ is constructed by modifying $G_{n-1}$ in some "systematic" way. in this particular case $G_n$ is "more complex" than $G_{n-1}$ and generally has more edges/vertices.

Question:

What is some systematic method of determining the "basic differences" between $G_n$ and $G_{n-1}$? In some sense, how does one derive a "recurrence relation" like a formula that derives $G_n$ from $G_{n-1}$ (similar to [1] but instead of using integers as parameters, here with graphs as the parameters)? What are some famous examples of graph sequences like this, successfully analyzed in the literature?

Presumably this general question is undecidable for some contrived cases [exercise for reader] but is decidable for special cases. I am interested in the subset of decidable cases.

Background

This is an old problem that first occurred to me about 2 decades ago which to my knowledge has not been studied too much in particular but which seems significant. I have a particular algorithm in mind for generating $G_n$ from $G_{n-1}$ for which I suspect there is not much research (hint, see other question [2]), and might mention/further clarify at a later date; but for now I am interested in a more general approach.

Another analogy would be with textual "diff" programs which find lines added, deleted, modified between two text files. Is there an analogous approach for graphs that has been used somewhere? Actually, I suspect this type of construction is somewhat widespread in graph theory proofs, maybe even key/famous ones, but not necessarily studied so much in isolation.

In the best case scenario, there would be a software package that would actually successfully derive such formulas in some cases, but to my knowledge it does not exist right now.

[1] solving recurrence relations, wikipedia

[2] largest language class for which inclusion is decidable

Answer 1

I think your question falls in the context of "graph operators". A graph operator $S$ is just a map from the class of graphs to the class of graphs, and you then have a sequence $G$, $S(G)$, $S^2(G)$, etc.

I do not think that there could possibly be a general way to determine $S^n(G)$ as a function of $n$ and $G$ that could work for all $S$, even for a fixed $S$. For example, if $S(G)$ is the intersection graph of the maximal cliques of $G$ (considered in Harary's book and denoted by $K$), then what you ask is known for only a handful of families, including the complements of $nK_2$, the locally $C_6$ graphs and the so called "clockwork graphs".

Many other graph operators are studied in the book "Graph Dynamics" by Erich Prisner.