Kn1,...,nr denotes the complete r-partite graph of sets of nodes , ni = |Vi|. The edges are such that for every , the graph induced by Vi and Vj is a complete bipartite graph, Kni,nj. For instance, K1,...,1 = Kn.
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 graph6 defined by .
Finally, there are several works on Interval Routing with experimental approaches and simulation results: [Bra93,Jug93,HKR91,LW96,Sch97].