NOTE

Decomposition Duality

Reinhard Diestel

The purpose of this note is just to point out a duality aspect of graph decompositions that came up unexpectedly in the context of other investigations [ 1 ], but which can be presented briefly on its own and may be of independent interest. The duality we shall define generalizes the duality of plane graphs. It thus raises the question whether results based on the latter (such as colouringflow duality) can be extended or seen in a new light when viewed from a decomposition angle.

Let G, H be graphs. Consider a family D = (G_{h})_{h^{∈}H} of induced subgraphs of G indexed by the vertices of H. Let us call D an H-decomposition of G (into the parts G_{h}) if

(D1) every vertex of G lies in some G_{h}

(D2) given an edge e = gg′ ^{∈} G, either e lies in some G_{h} or there exists an edge hh′ ^{∈} H such that g ^{∈} G_{h} and g′ ^{∈} G_{h′}

and call this decomposition D connected if it also satisfies

(D3) whenever a vertex g ^{∈} G lies in G_{h_{1}} ∩ G_{h_{2}} for some h_{1}, h_{2} ^{∈} H, there is a path P = h_{1} … h_{2} in H such that g ^{∈} G_{h} for every h ^{∈} P.

When H is a tree, then this kind of decomposition is closely related to standard tree-decompositions; see [ 1 ].

For every g ^{∈} G define a subgraph H_{g} of H by setting

H_{g} = H [ { h | g ^{∈} G_{h} }] ,  (1)

and write

D^{∗} := (H_{g})_{g^{∈}G}  (2)

for the family of these subgraphs. We shall call the family D^{∗} the dual of the family D, and its parts H_{g} the co-parts of D.

It is possible to rewrite the conditions (D1)–(D3) more elegantly in terms of these co-parts. Recall that two subgraphs of a graph H are said to touch (in H) if they have a vertex in common or H contains an edge between them. Each of the conditions (D1)–(D3) is easily seen to be equivalent to the corresponding following condition:

(C1) every H_{g} is non-empty;

(C2) for every edge gg′ ^{∈} G, the graphs H_{g} and H_{g′} touch in H;

(C3) every H_{g} is connected.

The conditions (C1)–(C3) offer an alternative way to think of a given Hdecomposition of G: as a collection of subgraphs of H rather than of G. Indeed, presenting D^{∗} instead of D entails no loss of information. For given any two vertices g ^{∈} G and h ^{∈} H, clearly (1) implies that

g ^{∈} G_{h} ⇔ h ^{∈} H_{g}  (3)

and hence that

G_{h} = G [ { g | h ^{∈} H_{g} }] ,  (4)

the dual statement to (1). So the G_{h} can be reobtained from the H_{g}, and they are obtained from them in exactly the same way as the H_{g} were obtained from the G_{h}. Thus,

D^{∗∗} = D.

Now it may or may not happen that the family D^{∗} = (H_{g})_{g^{∈}G} obtained from our H-decomposition D = (G_{h})_{h^{∈}H} is in turn a G-decomposition of H. Let us call D invertible if this is the case. By (4), the conditions (C1)–(C3) for when this happens translate as follows:

Proposition 1. D is invertible if and only if (I1) every G_{h} is non-empty; (I2) for every edge hh′ ^{∈} H, the parts G_{h} and G_{h′} touch in G.

The dual decomposition D^{∗} of D will be connected if and only if

(I3) every G_{h} is connected. □

The ‘message’ of translating the conditions on D^{∗} into statements about D in this way is that D is invertible as soon as H has no more vertices or edges than are required for D to satisfy (D1) and (D2). Thus we can make any H-decomposition invertible simply by deleting superfluous vertices and edges of H. (This technique turned out to be surprisingly useful in [ 2 ].)

Given a pair of dual decompositions D and D^{∗} as above, one might at first be tempted also to think of H as a dual of G, and vice versa. However, given a graph G there is no unique H such that G has an invertible H-decomposition.

For example, every graph G ≠ ∅ has two trivial invertible decompositions: the K_{1}-decomposition into just one part G, and the G-decomposition into singletons, ie. with G_{g} = { g }. More generally, for every graph H that contains G as a minor, G has the connected H-decomposition (G_{h})_{h^{∈}H} into singletons defined by choosing as H_{g} the subgraph of H induced by the branch set corresponding to g. If G is even an MH, ie. obtained just by contraction without deletion, then (I1) and (I2) hold while (I3) is void, so this decomposition is invertible.

However, what we might ask for is a canonical way of obtaining such dual graphs and decompositions:

Problem 2. For which classes C of finite graphs can we assign in a non-trivial way to every graph G ^{∈} C a graph G^{∗} ^{∈} C and an invertible G^{∗}-decomposition D(G) of G so that G^{∗∗} = G and D(G^{∗}) = D^{∗}(G)?

Here, D^{∗}(G) denotes the dual of the decomposition D(G). The definition of ‘non-trivial’ will have to be adjusted to need; for example, it should probably preclude most choices of G^{∗} and D(G) with G^{∗} = G.

Abstract though this may seem, there is a well-known instance of this kind of duality: the duality of planar graphs. Indeed, if G is a planar graph (3-connected, say, to make its drawing unique) and G^{∗} is its planar dual, then the obvious G^{∗}-decomposition of G into its face boundaries satisfies all the requirements of Problem 2. A special case of this problem, therefore, would be to ask for C to extend the class of planar graphs and for G^{∗} and D(G) to coincide with planar duality and face decompositions when G is planar. For example:

Problem 3. Can the flow-colouring duality for plane graphs be extended to a larger class based on decomposition duality?

It should be pointed out that interpreting planar duality as decomposition duality in this way is, so far, no more than a restatement, carrying no ‘substance’. The hope, however, is that viewing this duality from a decomposition angle might guide attempts to generalize planar duality in ways that are natural in a decomposition context but might otherwise not be obvious.

References

[1] R. Diestel & D. Kühn, Graph minor hierarchies, preprint 2001 (on this server).

[2] R. Diestel & D. Kühn, Tree hierarchies, manuscripts 2000.