Constructive characterization of dumpy graphs
Find a constructive characterization of k-dumpy graphs.
For the case when k=2 the following constructive characterization can be proved :
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.
- K. Bérczi and E.R. Kovács, Constructive characterization of dumpy digraphs, EGRES Quick Proof no. 2011-05