| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 419357 | Discrete Applied Mathematics | 2013 | 7 Pages |
The average connectivity κ¯(G) of a graph GG is the average, over all pairs of vertices, of the maximum number of internally disjoint paths connecting these vertices. The connectivity κ(G)κ(G) can be seen as the minimum, over all pairs of vertices, of the maximum number of internally disjoint paths connecting these vertices. The connectivity and the average connectivity are upper bounded by the minimum degree δ(G)δ(G) and the average degree d¯(G) of GG, respectively. In this paper the average connectivity of the strong product G1⊠G2G1⊠G2 of two connected graphs G1G1 and G2G2 is studied. A sharp lower bound for this parameter is obtained. As a consequence, we prove that κ¯(G1⊠G2)=d¯(G1⊠G2) if κ¯(Gi)=d¯(Gi), i=1,2i=1,2. Also we deduce that κ(G1⊠G2)=δ(G1⊠G2)κ(G1⊠G2)=δ(G1⊠G2) if κ(Gi)=δ(Gi)κ(Gi)=δ(Gi), i=1,2i=1,2.
