A note on minimum degree conditions for supereulerian graphs
type: Item
instance of: scholarly article
title: A note on minimum degree conditions for supereulerian graphs
zbMATH Open document ID: 0993.05097
DOI: 10.1016/S0166-218X(01)00278-5
published in: Discrete Applied Mathematics
publication date: 2002-08-29T00:00:00Z
review text: A graph is supereulerian if it has a spanning eulerian subgraph. The main result of the paper states that if \(G\) is a simple \(2\)-edge-connected graph of order \(n\) such that for every minimal edge cut \(S\) with \(|S|\leq 3\) every component of \(G-S\) has order at least \((n-2)/5>2\), then \(G\) is either supereulerian or belongs to one of two well-described classes of exceptions. The authors derive this result relatively easily from a result due to Catlin. As a consequence they prove that if \(G\) is a \(2\)-edge-connected graph of order \(n\) and minimum degree at least \(4\) such that \(\max\{ d(x),d(y)\}\geq (n-2)/5-1\) for every edge \(xy\) of \(G\), then \(G\) is either supereulerian or belongs to one of two well-described classes of exceptions. This is a slight improvement of a result of \textit{P. A. Catlin} and \textit{X. Li} [Adv. Math., Beijing 28, 65-70 (1999; Zbl 1054.05506)].
reviewed by: Dieter Rautenbach
Mathematics Subject Classification ID: 05C45
Mathematics Subject Classification ID: 05C35
zbMATH DE Number: 1792310
zbMATH Keywords: supereulerian graph
author: Hajo Broersma
author: Liming Xiong
MaRDI profile type: Publication
cites work: On circuits and pancyclic line graphs
cites work: Q5422499
cites work: On factors of 4-connected claw-free graphs
cites work: Supereulerian graphs: A survey
cites work: Spanning Eulerian subgraphs and matchings
cites work: A reduction method to find spanning Eulerian subgraphs
cites work: Super-Eulerian graphs of minimum degree at least \(4\).
cites work: Q3983243
cites work: On Eulerian and Hamiltonian Graphs and Line Graphs
cites work: A Note on Sub-Eulerian Graphs
cites work: Eulerian subgraphs containing given vertices and hamiltonian line graphs
cites work: On dominating and spanning circuits in graphs
description: scientific article; zbMATH DE number 1792310