Distance

Topological properties of the representation may be reflected in the intersection graph. Even metric properties, like distance, sometimes show through.

Why is every power of an interval graphs an interval graphs, but not every power of a unit interval graph a unit interval graph? Why are odd powers of chordal graphs chordal, but the even powers not necessarily?

Let G be the intersection graph of the hypergraphs H=(A,(S_x/x V)). Then distances in G can be expressed by set intersection of the sets S_x^t, where S_x¹ :=S_x and S_x^t is recursively defined. We get d_G(x,y) i+j-1 if and only if S_xⁱ S_y^j is nonempty. Therefore (A,(S_x^t/x V)) is a intersection representation of the (2t-1)th power of G, whose vertices are adjacent if and only if d_G(x,y) 2t. In some situations, these sets S_x^t have the same shape than the original sets S_x. For instance, if the only property P the sets S_x have to be obey is, that they should be connected subsets of some topological space, then the sets S_x^t are also connected subsets of it. Then every odd power of a graph in G(P) lies again in G(P). A prominent example is the classe of chordal graphs

[BP83], [D84]: Odd powers of chordal graphs are chordal.

But we get an odd power result also for circular-arc graphs or interval graphs in this way.

What about even powers? Here we need geometric models with ordering. Assume G is the intersection graph of P-sets S_x, where for every two disjoint sets, one is to the left of the other. Assume furthermore that S_y \ S_x divides naturally into two parts, one to the left and the other to the right of S_x. Then we may define R_x as the union of S_x and all right parts of S_y \ S_x for neighbors y of x. It turns out that these sets R_x are an intersection representation of G². The only problem may be that these sets are not necessarily P-sets. In some cases, however, we may replace them by P-sets having the same intersection pattern than the sets R_x.

If the S_x^t-construction above applies also, we get representations of all powers of G by P-sets in that case.

This approach works for intervals on the real line without further ado. It works for trapezoids between two parallel lines by taking the convex hulls of the sets R_x constructed (which are no trapezoids). It even works for structures with some cyclic ordering, as for connected subsets (circular arcs) of the unit circle.

[R87] All powers of interval graphs are interval graphs. [F95] All powers of trapezoid graphs are trapezoid graphs. [D92] All powers of cocomparability graphs are cocomparability graphs. [R92] All powers of circular-arc graphs are circular-arc graphs.

A. Raychaudhouri posed the problem whether or not it is true that whenever Gk is a circular-arc graph, then Gk+1 must too be a circular-arc graph.

There are several other situations where the distances transfer, let me just mention one more example for line graphs and clique graphs:

[H84], [H86]: For every graph G, diam(G)-1 diam(L(G) diam(G)+1, as well as diam(G)-1 diam(C(G) diam(G)+1.

Back to the start page for intersection graphs.