You may notice that there is some connection between this and this example. In the first we have the intersection graph of all attendance lists of the courses, whereas in the second we are considering the intersection graph of all course lists of the students. Both sets of lists obviously contain the same information. Each one is the dual of the other.

Duality is the most important, yet very natural,
notion for intersection graphs.
Assume there is a hypergraph *H=(A,(S _{x}/x
V))*.
For every

The hypergraph *(V,(a*/a
A))* is called the
**dual hypergraph** *H** of *H*.
Look at an example.

It should be clear that the dual hypergraph
contains the same information as the original one,
in fact it can easily be retrieved from the dual since
*H = (H*)**.

This essentially
formal definition gets life by looking
on intersection graphs.
Let us consider the intersection graph *G=(V,E)* of the hypergraph
*H=(A,(S _{x}/x
V))*.
Then the dual hyperedges

- Every star graph is complete, and
- The set of all star graphs forms an
**edge cover**of*G*, i.e. every edge of*G*lies in at least one star graph.

Intersection graphs can also be defined by duality.
The **underlying graph** (sometimes called **1-skeleton**)
of a hypergraph *H=(A,(S _{x}/x
V))* has the same
vertex set

Note that in geometric intersection models there may be infinitely many star graphs, however only finitely many distinct. Moreoever, since most of these geometric models are stable under slight pertuberations, we may assume in most cases that every star graph occuring occurs infinitely often.

Is there any connection between intersection graphs of dual
hypergraphs? Given two graphs
G and
_{1}G, can you construct a hypergraph _{2}H
such that G = _{1}
(H) and
G = _{2}
(H?^{*}) |

For an example take the special case of competition and resource graphs of a digraph---they are intersection graphs of the family of all out-neighborhoods respectively in-neighborhoods, which are obviously dual to each other.

Duality is used for some natural approach for the recognition problem.

Now you may be interested in the special role of cliques in intersection graphs or go back to the start page for intersection graphs.

Erich Prisner

made on January 12, 1999