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].