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).
Keywords:
- Correction
- Source
- Cite
- Save
- Machine Reading By IdeaReader
19
References
7
Citations
NaN
KQI