** Next:** Graph Operators
** Up:** Specific Class of Graphs
** Previous:** Random Graphs
** Contents**

##

Other Classes of Graphs

*K*_{n1,...,nr} denotes the complete *r*-partite graph of sets of
nodes
,
*n*_{i} = |V_{i}|. The edges are
such that for every ,
the graph induced by *V*_{i} and *V*_{j}
is a complete bipartite graph, *K*_{ni,nj}. For instance,
*K*_{1,...,1} = *K*_{n}.

This has been slightly improved later for bipartite graphs (improving
also a result of Theorem 20):

The next class of graphs includes complete graphs, paths and rings.
See [Gol80] for an introduction to these classes of graphs.
Note that the class of unit interval graphs corresponds with the
class of proper interval graphs.

The latter result has been extended to the interval graphs (this class
includes trees):

By an exhaustive computation of all the possible labeling, we found
that the Petersen graph, *P*, satisfies
.
*P*=(*V*,*E*) is an intersection
graph^{6} defined by
.

Finally, there are several works on Interval Routing with experimental
approaches and simulation results:
[Bra93,Jug93,HKR91,LW96,Sch97].

** Next:** Graph Operators
** Up:** Specific Class of Graphs
** Previous:** Random Graphs
** Contents**

*2000-03-21*