** 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 *G*_{1}=(*V*_{1},*E*_{1}) with *G*_{2}=(*V*_{2},*E*_{2}),
denoted by ,
has the node set ,
and the
edge set
and [(*u*_{1}=*v*_{1} and
or (*u*_{2}=*v*_{2} and
.

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,
.
The -torus is a counterexample. In [FG98], other results are
mentioned about the *k*-dilation in Cartesian product.

**Open question 11**
*
*

- Does
imply
for every ? (where *C*_{n} denotes an *n*-node
cycle)*
*
The *composition* of *G*_{1}=(*V*_{1},*E*_{1}) with *G*_{2}=(*V*_{2},*E*_{2}),
denoted by *G*_{1}[*G*_{2}], has the node set ,
and the edge
set
and either
or (*u*_{1}=*v*_{1} and
.
The
previous result of [KKR93] has been improved with:

In the following,
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*_{1}=(*V*_{1},*E*_{1}) with *G*_{2}=(*V*_{2},*E*_{2}),
denoted by *G*_{1}+*G*_{2}, has the node set ,
and the edge
set
.

** Next:** Summary
** Up:** Specific Class of Graphs
** Previous:** Other Classes of Graphs
** Contents**

*2000-03-21*