Skip to main content
Article
Spanning Eulerian subgraphs and Catlin’s reduced graphs
Journal of Combinatorial Mathematics and Combinatorial Computing
  • Wei-Guo Chen
  • Zhi-Hong Chen, Butler University
Document Type
Article
Publication Date
2-1-2016
Disciplines
Abstract

A graph G is collapsible if for every even subset R ⊆ V (G), there is a spanning connected subgraph HR of G whose set of odd degree vertices is R. A graph is reduced if it has no nontrivial collapsible subgraphs. Catlin [4] showed that the existence of spanning Eulerian subgraphs in a graph G can be determined by the reduced graph obtained from G by contracting all the collapsible subgraphs of G. In this paper, we present a result on 3-edge-connected reduced graphs of small orders. Then, we prove that a 3-edge-connected graph G of order n either has a spanning Eulerian subgraph or can be contracted to the Petersen graph if G satisfies one of the following:

(i) d(u) + d(v) > 2(n/15 − 1) for any uv 6∈ E(G) and n is large;

(ii) the size of a maximum matching in G is at most 6;

(iii) the independence number of G is at most 5.

These are improvements of prior results in [16], [18], [24] and [25].

Rights

This is a post-print version of an article originally published in Journal of Combinatorial Mathematics and Combinatorial Computing, 2016, Volume 96.

The version of record is available through: WorldCat.

Citation Information
Wei-Guo Chen and Zhi-Hong Chen. "Spanning Eulerian subgraphs and Catlin’s reduced graphs" Journal of Combinatorial Mathematics and Combinatorial Computing Vol. 96 (2016) p. 41 - 63
Available at: http://works.bepress.com/zhi_hong_chen/26/