On removable even circuits in graphs

Let G be a connected graph with minimum degree at least 3. We prove that there exists an even circuit C in G such that G− E( C) is either connected or contains precisely two components one of which is isomorphic to a 1-bond. We further prove sufficient conditions for there to exist an even circuit C...

Full description

Saved in:
Bibliographic Details
Published in:Discrete mathematics 2004-09, Vol.286 (3), p.177-184
Main Author: Sinclair, P.A.
Format: Article
Language:English
Subjects:
Combinatorics
Combinatorics. Ordered structures
Exact sciences and technology
Graph theory
Mathematics
Removable even circuits
Sciences and techniques of general use
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Let G be a connected graph with minimum degree at least 3. We prove that there exists an even circuit C in G such that G− E( C) is either connected or contains precisely two components one of which is isomorphic to a 1-bond. We further prove sufficient conditions for there to exist an even circuit C in a 2-connected simple graph G such that G− E( C) is 2-connected. As a consequence of this, we obtain sufficient conditions for there to exist an even circuit C in a 2-connected graph G for which G− E( C) is 2-connected.
ISSN:0012-365X
1872-681X
DOI:10.1016/j.disc.2004.03.012