کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
421411 | 684221 | 2007 | 12 صفحه PDF | دانلود رایگان |
![عکس صفحه اول مقاله: On the edge-connectivity and restricted edge-connectivity of a product of graphs On the edge-connectivity and restricted edge-connectivity of a product of graphs](/preview/png/421411.png)
The product graph Gm*GpGm*Gp of two given graphs GmGm and GpGp was defined by Bermond et al. [Large graphs with given degree and diameter II, J. Combin. Theory Ser. B 36 (1984) 32–48]. For this kind of graphs we provide bounds for two connectivity parameters (λλ and λ′λ′, edge-connectivity and restricted edge-connectivity, respectively), and state sufficient conditions to guarantee optimal values of these parameters. Moreover, we compare our results with other previous related ones for permutation graphs and cartesian product graphs, obtaining several extensions and improvements. In this regard, for any two connected graphs GmGm, GpGp of minimum degrees δ(Gm)δ(Gm), δ(Gp)δ(Gp), respectively, we show that λ(Gm*Gp)λ(Gm*Gp) is lower bounded by both δ(Gm)+λ(Gp)δ(Gm)+λ(Gp) and δ(Gp)+λ(Gm)δ(Gp)+λ(Gm), an improvement of what is known for the edge-connectivity of Gm×GpGm×Gp.
Journal: Discrete Applied Mathematics - Volume 155, Issue 18, 1 November 2007, Pages 2444–2455