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


On super 2-restricted and 3-restricted edge-connected vertex transitive graphs
Authors:Weihua Yang  Zhao Zhang  Chengfu Qin  Xiaofeng Guo
Institution:1. School of Mathematical Science, Xiamen University, Xiamen Fujian 361005, China;2. College of Mathematics and Systems Sciences, Xinjiang University, Urumqi 830046, China
Abstract:Let G=(V(G),E(G)) be a simple connected graph and F?E(G). An edge set F is an m-restricted edge cut if G?F is disconnected and each component of G?F contains at least m vertices. Let λ(m)(G) be the minimum size of all m-restricted edge cuts and ξm(G)=min{|ω(U)|:|U|=m and GU] is connected}, where ω(U) is the set of edges with exactly one end vertex in U and GU] is the subgraph of G induced by U. A graph G is optimal-λ(m) if λ(m)(G)=ξm(G). An optimal-λ(m) graph is called super m-restricted edge-connected if every minimum m-restricted edge cut is ω(U) for some vertex set U with |U|=m and GU] being connected. In this note, we give a characterization of super 2-restricted edge-connected vertex transitive graphs and obtain a sharp sufficient condition for an optimal-λ(3) vertex transitive graph to be super 3-restricted edge-connected. In particular, a complete characterization for an optimal-λ(2) minimal Cayley graph to be super 2-restricted edge-connected is obtained.
Keywords:
本文献已被 ScienceDirect 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

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