Premium
On removable circuits in graphs and matroids
Author(s) -
Lemos Manoel,
Oxley James
Publication year - 1999
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/(sici)1097-0118(199901)30:1<51::aid-jgt6>3.0.co;2-7
Subject(s) - mathematics , combinatorics , matroid , graphic matroid , conjecture , dual graph , discrete mathematics , graph , line graph
Mader proved that every 2‐connected simple graph G with minimum degree d exceeding three has a cycle C , the deletion of whose edges leaves a 2‐connected graph. Jackson extended this by showing that C may be chosen to avoid any nominated edge of G and to have length at least d − 1. This article proves an extension of Jackson's theorem. In addition, a conjecture of Goddyn, van den Heuvel, and McGuinness is disproved when it is shown that a natural matroid dual of Mader's theorem fails. © 1999 John Wiley & Sons, Inc. J Graph Theory 30: 51–66, 1999