کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
428611 | 686840 | 2011 | 4 صفحه PDF | دانلود رایگان |
![عکس صفحه اول مقاله: On edge connectivity of direct products of graphs On edge connectivity of direct products of graphs](/preview/png/428611.png)
Let λ(G)λ(G) be the edge connectivity of G. The direct product of graphs G and H is the graph with vertex set V(G×H)=V(G)×V(H)V(G×H)=V(G)×V(H), where two vertices (u1,v1)(u1,v1) and (u2,v2)(u2,v2) are adjacent in G×HG×H if u1u2∈E(G)u1u2∈E(G) and v1v2∈E(H)v1v2∈E(H). We prove that λ(G×Kn)=min{n(n−1)λ(G),(n−1)δ(G)}λ(G×Kn)=min{n(n−1)λ(G),(n−1)δ(G)} for every nontrivial graph G and n⩾3n⩾3. We also prove that for almost every pair of graphs G and H with n vertices and edge probability p , G×HG×H is k -connected, where k=O((n/logn)2)k=O((n/logn)2).
► We give the edge connectivity of the direct product of a graph and a complete graph.
► We give the edge connectivity of the direct product of a graph and a total graph.
► The direct product of almost every pair of graphs in Gn,pGn,p is O((n/logn)2)O((n/logn)2)-connected.
Journal: Information Processing Letters - Volume 111, Issue 18, 30 September 2011, Pages 899–902