next up previous contents
Next: Graph Operators Up: Specific Class of Graphs Previous: Random Graphs   Contents


Other Classes of Graphs

Kn1,...,nr denotes the complete r-partite graph of sets of nodes $V = V_1 \cup \ldots \cup V_r$, ni = |Vi|. The edges are such that for every $i \neq j$, the graph induced by Vi and Vj is a complete bipartite graph, Kni,nj. For instance, K1,...,1 = Kn.


\begin{theorem}[\cite{KKR93}]
For every $2 \leqs n_1 \leqs \ldots, \leqs n_r$, $\mbox{\rm LIRS}(K_{n_1,\ldots,n_r}) = 1$.
\end{theorem}

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


\begin{theorem}[\cite{NS96}]
\mbox{}
\beginsmall{itemize}
\item For every $1 \le...
...leqs n_2$, $\mbox{\rm SLIRS}(K_{n_1,n_2}) = 1$.
\endsmall{itemize}
\end{theorem}

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.


\begin{theorem}[\cite{FG98a}]\mbox{}
\beginsmall{itemize}
\item $\mbox{\rm SIRS}...
...box{\rm LIRS}(\mbox{\em interval graphs}) > 1$. \endsmall{itemize}
\end{theorem}

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


\begin{theorem}[\cite{NS96}]
$\mbox{\rm SIRS}(\mbox{\em interval graphs}) = 1$.
\end{theorem}

By an exhaustive computation of all the possible labeling, we found that the Petersen graph, P, satisfies $\mbox{\rm SLIRS}(P) = \mbox{\rm LIRS}(P) =
\mbox{\rm SIRS}(P) = \mbox{\rm IRS}(P) = 3$. P=(V,E) is an intersection graph6 defined by $V = \{ X \subseteq
\{1,\ldots,5\} \mid \vert X\vert=2 \}$.

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


next up previous contents
Next: Graph Operators Up: Specific Class of Graphs Previous: Random Graphs   Contents

2000-03-21