Premium
On removable cycles through every edge
Author(s) -
Lemos Manoel,
Oxley James
Publication year - 2003
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.10082
Subject(s) - combinatorics , mathematics , graph , simple graph , connectivity , enhanced data rates for gsm evolution , disjoint sets , simple (philosophy) , discrete mathematics , computer science , artificial intelligence , philosophy , epistemology
Mader and Jackson independently proved that every 2‐connected simple graph G with minimum degree at least four has a removable cycle, that is, a cycle C such that G / E ( C ) is 2‐connected. This paper considers the problem of determining when every edge of a 2‐connected graph G , simple or not, can be guaranteed to lie in some removable cycle. The main result establishes that if every deletion of two edges from G remains 2‐connected, then, not only is every edge in a removable cycle but, for every two edges, there are edge‐disjoint removable cycles such that each contains one of the distinguished edges. © 2002 Wiley Periodicals, Inc. J Graph Theory 42: 155–164, 2003