# Constructive characterization of dumpy graphs

Find a constructive characterization of k-dumpy graphs.

## Remarks

For the case when k=2 the following constructive characterization can be proved [1]:

Every 2-dumpy graph can be built up from three parallel edges by the consecutive application of the following three steps:

(i) adding a new node to the graph with two non-parallel edges entering it,

(ii) subdividing an existing edge with a new node and adding a new edge entering it so that no parallel edges arise,

(iii) reorienting a dicircuit.

There is an example where step (iii) cannot be omitted from the construction.

The k=2 case has a motivation from rigidity. Let G=(V,E) be a two-dimensional minimally rigid graph. By adding an extra node r to G and connecting it to nodes x and y with one and two edges, respectively, one gets a graph that has a rooted 2-edge connected orientation from r (this can be proved easily using that G is a (2,3)-graph). Such an orientation gives a 2-dumpy graph. Hence the constructive characterization of dumpy graphs for the case k=2 gives a new proof of the Henneberg construction. Not surprisingly, the proof relies on the same ideas as the one for the undirected case.

## References

1. K. Bérczi and E.R. Kovács, Constructive characterization of dumpy digraphs, EGRES Quick Proof no. 2011-05