Constructive characterization of dumpy graphs

From Egres Open
Jump to: navigation, search

Find a constructive characterization of k-dumpy graphs.


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.


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