On edge connectivity of direct products of graphs
Abstract
Let λ(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), where two vertices (u1,v1) and (u2,v2) are adjacent in G×H if u1u2∈E(G) and v1v2∈E(H). We prove that λ(G×Kn)=min{n(n−1)λ(G),(n−1)δ(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, G×H is k-connected, where...
Paper Details
Title
On edge connectivity of direct products of graphs
Published Date
Sep 1, 2011
Volume
111
Issue
18
Pages
899 - 902
Citation AnalysisPro
You’ll need to upgrade your plan to Pro
Looking to understand the true influence of a researcher’s work across journals & affiliations?
- Scinapse’s Top 10 Citation Journals & Affiliations graph reveals the quality and authenticity of citations received by a paper.
- Discover whether citations have been inflated due to self-citations, or if citations include institutional bias.
Notes
History