Other Classes of Graphs

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

Other Classes of Graphs

K_{n₁,...,n_r} denotes the complete r-partite graph of sets of nodes $V = V_1 \cup \ldots \cup V_r$ , n_i = |V_i|. The edges are such that for every $i \neq j$ , the graph induced by V_i and V_j is a complete bipartite graph, K_{n_i,n_j}. For instance, K_1,...,1 = K_n.

$\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 graph⁶ 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: Graph Operators Up: Specific Class of Graphs Previous: Random Graphs Contents

2000-03-21