On super 2-restricted and 3-restricted edge-connected vertex transitive graphs

详细信息    查看全文

• 作者：Weihua  ; Yang^a ;   ; ^{ywh222@163.com} ; Zhao  ; Zhang^b ; Chengfu  ; Qin^a ; Xiaofeng  ; Guo^a
• 关键词：Restricted edge-connectivity ; Super edge-connected ; Transitive graph ; Cayley graph
• 刊名：Discrete Mathematics
• 出版年：2011
• 出版时间：28 December 2011
• 年：2011
• 卷：311
• 期：23-24
• 页码：2683-2689
• 全文大小：233 K

文摘

Let be a simple connected graph and . An edge set is an -restricted edge cut if is disconnected and each component of contains at least vertices. Let be the minimum size of all -restricted edge cuts and , where is the set of edges with exactly one end vertex in and is the subgraph of induced by . A graph is optimal- if . An optimal- graph is called super -restricted edge-connected if every minimum -restricted edge cut is for some vertex set with and 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- vertex transitive graph to be super 3-restricted edge-connected. In particular, a complete characterization for an optimal- minimal Cayley graph to be super 2-restricted edge-connected is obtained.