<p>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 <a href="https://en.wikipedia.org/wiki/Clique-width" rel="nofollow noreferrer">clique-width</a>. 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.</p>

CC BY-SA 3.0
2017-05-25T13:04:29.970Z
In particular any "tree like" decomposition of a graph can usually be translated into a way of writing the graph as a "sum" of "parts". So tree decompositions, split/modular decompositions, and the strucural decompositions for perfect/claw-free/etc. graphs can be thought of in this way. For different decompositions the correspondence is more or less strong.
daniello
CC BY-SA 3.0
2017-05-24T20:02:48.437Z
2017-05-24T20:02:48.437Z
David Eppstein
<p>1) Hajos calculus for non-$k$-colorability. Using the <a href="https://en.wikipedia.org/wiki/Haj%C3%B3s_construction" rel="nofollow noreferrer">Hajos construction</a>, one defines a notion of $k$-constructible graph as follows: </p>

<ul>
<li><p>the complete graph $K_k$ is $k$-constructible</p></li>
<li><p>taking two $k$-constructible graphs and applying the  yields a $k$-constructible graph</p></li>
<li><p>identifying two vertices preserves $k$-constructibility. </p></li>
</ul>

<p>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.</p>

<p>2) Although not about graphs in particular, people have also studied <a href="https://en.wikipedia.org/wiki/Circuits_over_sets_of_natural_numbers" rel="nofollow noreferrer">circuits over sets of natural numbers</a>. 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.</p>

CC BY-SA 3.0
2017-05-24T19:38:17.750Z
2017-05-24T19:38:17.750Z
Joshua Grochow
<p>An <em>addition chain</em> 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.</p>

<p>I wonder if "graph addition chains" have been studied, most probably under different names. For a graph $G$, a <em>graph addition chain</em> could be a sequence of graphs
$$G_0,\ldots,G_l =G$$
such that $G_0$ is contained in <strong>some set</strong> $\mathcal{F}$ of elementary graphs, and each $G_t$ is <strong>some sum</strong> 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). </p>

<p>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.</p>

<p>I would be thankful for any references to algorithmic and structural results about this or related concepts.</p>

CC BY-SA 3.0
2012-07-13T23:20:43.893Z
Not an answer, but note that the minimum length of an addition chain is nothing but the minimum size of circuits consisting of the constant-1 gate and the binary addition gate.  So another way to state “graph addition chain” is a circuit where each gate has a graph as a value and each internal node performs a certain operation on graphs.
Tsuyoshi Ito
<ds.algorithms><reference-request><graph-theory><co.combinatorics><treewidth>
Graph addition chains
Radu Curticapean
# Graph addition chains

(Asked by: username_0 on 2012-07-13)

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.

**Tags:** ds.algorithms, reference-request, graph-theory, co.combinatorics, treewidth
> **Comments:**
> **username_1**: Not an answer, but note that the minimum length of an addition chain is nothing but the minimum size of circuits consisting of the constant-1 gate and the binary addition gate.  So another way to state “graph addition chain” is a circuit where each gate has a graph as a value and each internal node performs a certain operation on graphs.  

---

## 2 answers

### Answer by username_2 on 2017-05-24. Score: 2

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](https://en.wikipedia.org/wiki/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.

> **Comments:**
> **username_3**: In particular any "tree like" decomposition of a graph can usually be translated into a way of writing the graph as a "sum" of "parts". So tree decompositions, split/modular decompositions, and the strucural decompositions for perfect/claw-free/etc. graphs can be thought of in this way. For different decompositions the correspondence is more or less strong.  

---

### Answer by username_4 on 2017-05-24. Score: 1

1) Hajos calculus for non-$k$-colorability. Using the [Hajos construction](https://en.wikipedia.org/wiki/Haj%C3%B3s_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](https://en.wikipedia.org/wiki/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.


---

