Super cyclically edge connected transitive graphs

Super cyclically edge connected transitive graphs

0.00 Avg rating0 Votes
Article ID: iaor201111125
Volume: 22
Issue: 4
Start Page Number: 549
End Page Number: 562
Publication Date: Nov 2011
Journal: Journal of Combinatorial Optimization
Authors: ,
Keywords: heuristics
Abstract:

A cyclic edge‐cut of a graph G is an edge set, the removal of which separates two cycles. If G has a cyclic edge‐cut, then it is called cyclically separable. For a cyclically separable graph G, the cyclic edge‐connectivity λ c (G) is the cardinality of a minimum cyclic edge‐cut of G. We call a graph super cyclically edge‐connected, if the removal of any minimum cyclic edge‐cut results in a component which is a shortest cycle. In this paper, we show that a connected vertex‐transitive or edge‐transitive graph is super cyclically edge‐connected if either G is cubic with girth g(G)≥7, or G has minimum degree δ(G)≥4 and girth g(G)≥6.

Reviews

Required fields are marked *. Your email address will not be published.