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

Open question 11
- Does imply for every ? (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 , 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 .

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

2000-03-21