On edge connectivity of direct products of graphs

2011 
Let @l(G) be the edge connectivity of G. The direct product of graphs G and H is the graph with vertex set V(GxH)=V(G)xV(H), where two vertices (u"1,v"1) and (u"2,v"2) are adjacent in GxH if u"1u"2@?E(G) and v"1v"2@?E(H). We prove that @l(GxK"n)=min{n(n-1)@l(G),(n-1)@d(G)} for every nontrivial graph G and n>=3. We also prove that for almost every pair of graphs G and H with n vertices and edge probability p, GxH is k-connected, where k=O((n/logn)^2).
    • Correction
    • Source
    • Cite
    • Save
    • Machine Reading By IdeaReader
    19
    References
    7
    Citations
    NaN
    KQI
    []