Super‐cyclically edge‐connected regular graphs

Super‐cyclically edge‐connected regular graphs

0.00 Avg rating0 Votes
Article ID: iaor20134028
Volume: 26
Issue: 2
Start Page Number: 393
End Page Number: 411
Publication Date: Aug 2013
Journal: Journal of Combinatorial Optimization
Authors: ,
Keywords: combinatorial optimization
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. We call a cyclically separable graph super cyclically edge‐connected, in short, super‐λ c , if the removal of any minimum cyclic edge‐cut results in a component which is a shortest cycle. In Z. Zhang, B. Wang (2011), it is proved that a connected edge‐transitive graph is super‐λ c if either G is cubic with girth at least 7 or G has minimum degree at least 4 and girth at least 6, and the authors also conjectured that a connected graph which is both vertex‐transitive and edge‐transitive is always super cyclically edge‐connected. In this article, for a λ c ‐optimal but not super‐λ c graph G, all possible λ c ‐superatoms of G which have non‐empty intersection with other λ c ‐superatoms are determined. This is then used to give a complete classification of non‐super‐λ c edge‐transitive k(k≥3)‐regular graphs.

Reviews

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