Graph addition chains

Question

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.

Answer 1

Sequences of colored graphs under the operations of disjoint union (a form of graph addition), recoloring, and adding edges between all vertices with some color combination form the basis for the definition of clique-width. However, the quantity of interest for measuring the complexity of such a sequence is not the number of operations needed, but the number of colors.

Answer 2

1) Hajos calculus for non-$k$-colorability. Using the Hajos construction, one defines a notion of $k$-constructible graph as follows:

• the complete graph $K_k$ is $k$-constructible

• taking two $k$-constructible graphs and applying the yields a $k$-constructible graph

• identifying two vertices preserves $k$-constructibility.

Every $k$-critical graph (requires $k$ colors but every subgraph needs at most $k-1$ colors) is $k$-constructible, and for all graphs $G$ $\chi(G) \geq k$ iff $G$ contains a $k$-constructible subgraph. This is a bit more complicated than what you asked for, since you'd also need to allow adding vertices, adding edges, and merging vertices, but it still feels like it's in the same spirit. The Hajos number of a $k$-colorable graph $G$ is the minimum number of steps needed to construct $G$ from $K_k$; there is no polynomial upper bound on the Hajos number unless NP=coNP.

2) Although not about graphs in particular, people have also studied circuits over sets of natural numbers. Here each input is a finite subset of $\mathbb{N}$, the gates are union, intersection, complement, + and times. So, in between (?) addition chains and graph addition chains, you might consider "subsets-of-$\mathbb{N}$" addition chains, by allowing only restricted inputs and a restricted gate set. As you can see from the Wikipedia table, several of the related problems are NP-complete, such as minimizing circuits with only $\cup, +$ gates (which might reasonably be considered "addition chains", esp. if you restrict the inputs to be all singletons, e.g.), or minimizing formulae with $\cup,\cap,+$ gates.