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 ,
has the node set
,
and the
edge set
and [(u1=v1 and
or (u2=v2 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.
The composition of G1=(V1,E1) with G2=(V2,E2),
denoted by G1[G2], has the node set ,
and the edge
set
and either
or (u1=v1 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 G1=(V1,E1) with G2=(V2,E2),
denoted by G1+G2, has the node set ,
and the edge
set
.