首页 | 本学科首页   官方微博 | 高级检索  
     


On edge connectivity of direct products of graphs
Authors:Xiang-Lan Cao  Elkin Vumar
Affiliation:a College of Mathematics and System Sciences, Xinjiang University, Urumqi 830046, PR China
b University of Maribor, FME, Smetanova 17, 2000 Maribor, Slovenia
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(GV(H), where two vertices (u1,v1) and (u2,v2) are adjacent in G×H if u1u2E(G) and v1v2E(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 k=O(2(n/logn)).
Keywords:Combinatorial problems  Connectivity  Direct product  Graph product  Separating set
本文献已被 ScienceDirect 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号