next up previous contents
Next: Summary Up: Specific Class of Graphs Previous: Other Classes of Graphs   Contents


Graph Operators

There are several results about some graph operators: Cartesian product, composition, and join of graphs.

The Cartesian product of G1=(V1,E1) with G2=(V2,E2), denoted by $G_1 \fois G_2$, has the node set $V_1 \fois V_2$, and the edge set $\{(u,v) \mid u=(u_1,u_2), v=(v_1,v_2),$ and [(u1=v1 and $(u_2,v_2) \in E_2)$ or (u2=v2 and $(u_1,v_1) \in E_1)]\}$.

The first point (the linear case) of Theorem 43 is due to [KKR93], the others due to [FG98]. The lower bounds of this theorem are obtained by application of Theorem 52 in Paragraph 4.1.


\begin{theorem}[\cite{KKR93,FG98a}]
\mbox{}
\beginsmall{itemize}
\item $\mbox{\...
...max\{\mbox{\rm LIRS}(G), \mbox{\rm SIRS}(H)\}$.
\endsmall{itemize}
\end{theorem}

We can see one motivation to distinguish the strictness and the linearity of IRS. To apply Theorem 43, one graph must support a strict IRS and the other a linear IRS. Note that, in general, $\mbox{\rm IRS}(G \fois H) \neq \max\{\mbox{\rm IRS}(G),\mbox{\rm IRS}(H)\}$. The $5\fois
5$-torus is a counterexample. In [FG98], other results are mentioned about the k-dilation in Cartesian product.

Open question 11    
- Does $\mbox{\rm LIRS}(G) \neq \mbox{\rm IRS}(G)$ imply $\mbox{\rm IRS}(G \fois C_n) \neq
\mbox{\rm IRS}(G)$ for every $n \geqs 5$? (where Cn denotes an n-node cycle)

The composition of G1=(V1,E1) with G2=(V2,E2), denoted by G1[G2], has the node set $V_1 \fois V_2$, and the edge set $\{(u,v) \mid u=(u_1,u_2), v=(v_1,v_2),$ and either $(u_1,v_1)\in
E_1$ or (u1=v1 and $(u_2,v_2) \in E_2)\}$. The previous result of [KKR93] has been improved with:


\begin{theorem}[\cite{NS96}]\mbox{}
\beginsmall{itemize}
\par\item $\mbox{\rm SL...
...IRS}(G[H]) \leqs
\mbox{\rm SIRS}(G)$.
\par\endsmall{itemize}
\par\end{theorem}

In the following, $\mbox{\rm SLIRS}^{\mbox{\rm\small tree}}(G)$ denotes the smallest k such that G supports an k-SLIRS such that from each node the routing paths induced by the k-SLIRS form a tree (see after Open Question 14, in Paragraph 4.6).


\begin{theorem}[\cite{dlTNP98}]
For any $H$, $\mbox{\rm SLIRS}^{\mbox{\rm\small tree}}(G[H]) \leqs
\mbox{\rm SLIRS}^{\mbox{\rm\small tree}}(G)$.
\end{theorem}

The join of G1=(V1,E1) with G2=(V2,E2), denoted by G1+G2, has the node set $V_1 \cup V_2$, and the edge set $E_1 \cup E_2 \cup \{(u,v) \mid u \in V_1, v \in V_2 \}$.


\begin{theorem}[\cite{KKR93}]
Suppose $G_1$\ and $G_2$\ are graphs with $n_1$\ a...
...where $f_i = \min\{n_i-\delta_i -1,\Delta_i+1\}$, $i \in \{1,2\}$.
\end{theorem}


next up previous contents
Next: Summary Up: Specific Class of Graphs Previous: Other Classes of Graphs   Contents

2000-03-21