An addition chain for $n \in \mathbb{N}$ is a sequence of natural numbers$$1 = a_0,\ldots,a_l =n$$such that each $a_t$ is the sum of two previous elements in the sequence. The length of minimal addition chains for natural numbers has been studied intensely.I wonder if graph addition chains have been studied, most probably under different names. For a graph $G$, a graph addition chain could be a sequence of graphs$$G_0,\ldots,G_l =G$$such that $G_0$ is contained in some set $\mathcal{F}$ of elementary graphs, and each $G_t$ is some sum of two previous elements. Depending on $\mathcal{F}$ and the sum operation, one could ask about the length of minimal graph addition chains (if they exist). As an example, set $\mathcal{F} = \{K_{k+1}\}$ and let the sum operation be the $k$-sum of graphs. Graph addition chains with these parameters produce partial $k$-trees, and we ask to construct partial $k$-trees using the minimal number of $k$-sums. For $k=1$, graph addition chains for path graphs correspond to addition chains for natural numbers, making this problem already $NP$-hard.I would be thankful for any references to algorithmic and structural results about this or related concepts.
Graph addition chains
ds.algorithms;reference request;graph theory;co.combinatorics;treewidth