✦ LIBER ✦

On removable circuits in graphs and matroids

✍ Scribed by Lemos, Manoel; Oxley, James

Publisher: John Wiley and Sons
Year: 1999
Tongue: English
Weight: 283 KB
Volume: 30
Category: Article
ISSN: 0364-9024
DOI: 10.1002/(sici)1097-0118(199901)30:1<51::aid-jgt6>3.0.co;2-7

No coin nor oath required. For personal study only.

✦ Synopsis

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.

📜 SIMILAR VOLUMES

On the Structure of 3-connected Matroids

On the Structure of 3-connected Matroids and Graphs

✍ James Oxley; Haidong Wu 📂 Article 📅 2000 🏛 Elsevier Science 🌐 English ⚖ 249 KB

An element e of a 3-connected matroid M is essential if neither the deletion M\e nor the contraction M/e is 3-connected. Tutte's Wheels and Whirls Theorem proves that the only 3-connected matroids in which every element is essential are the wheels and whirls. In this paper, we consider those 3-conne

Removable edges in 3-connected graphs

✍ Derek A. Holton; Bill Jackson; Akira Saito; Nicholas C. Wormald 📂 Article 📅 1990 🏛 John Wiley and Sons 🌐 English ⚖ 404 KB

## Abstract An edge __e__ of a 3‐connected graph __G__ is said to be __removable__ if __G__ ‐ __e__ is a subdivision of a 3‐connected graph. If __e__ is not removable, then __e__ is said to be __nonremovable.__ In this paper, we study the distribution of removable edges in 3‐connected graphs and pr

Cocircuit Graphs and Efficient Orientati

Cocircuit Graphs and Efficient Orientation Reconstruction in Oriented Matroids

✍ Eric Babson; Lukas Finschi; Komei Fukuda 📂 Article 📅 2001 🏛 Elsevier Science 🌐 English ⚖ 294 KB

We consider the cocircuit graph G M of an oriented matroid M, which is the 1-skeleton of the cell complex formed by the span of the cocircuits of M. As a result of Cordovil, Fukuda, and Guedes de Oliveira, the isomorphism class of M is not determined by G M , but it is determined if M is uniform and

Branch-Width and Well-Quasi-Ordering in

Branch-Width and Well-Quasi-Ordering in Matroids and Graphs

✍ James F. Geelen; A.M.H. Gerards; Geoff Whittle 📂 Article 📅 2002 🏛 Elsevier Science 🌐 English ⚖ 172 KB

Concept of a vertex in a matroid and 3-c

Concept of a vertex in a matroid and 3-connected graphs

✍ A. K. Kelmans 📂 Article 📅 1980 🏛 John Wiley and Sons 🌐 English ⚖ 316 KB

## Abstract The concept of a matroid vertex is introduced. The vertices of a matroid of a 3‐connected graph are in one‐to‐one correspondence with vertices of the graph. Thence directly follows Whitney's theorem that cyclic isomorphism of 3‐connected graphs implies isomorphism. The concept of a vert

Hamiltonian circuits in N2-locally conne

Hamiltonian circuits in N2-locally connected K1,3-free graphs

✍ ZdeněK Ryjáček 📂 Article 📅 1990 🏛 John Wiley and Sons 🌐 English ⚖ 407 KB 👁 1 views

## Abstract There are many results concerned with the hamiltonicity of __K__~1,3~‐free graphs. In the paper we show that one of the sufficient conditions for the __K__~1,3~‐free graph to be Hamiltonian can be improved using the concept of second‐type vertex neighborhood. The paper is concluded with