Graph Operators

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

The Cartesian product of G₁=(V₁,E₁) with G₂=(V₂,E₂), 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 [(u₁=v₁ and $(u_2,v_2) \in E_2)$ or (u₂=v₂ 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.

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 C_n denotes an n-node cycle)

The composition of G₁=(V₁,E₁) with G₂=(V₂,E₂), denoted by G₁[G₂], 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 (u₁=v₁ and $(u_2,v_2) \in E_2)\}$. The previous result of [KKR93] has been improved with:

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

The join of G₁=(V₁,E₁) with G₂=(V₂,E₂), denoted by G₁+G₂, 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 \}$.