Spanning Eulerian subgraphs and matchings
type: Item
instance of: scholarly article
title: Spanning Eulerian subgraphs and matchings
zbMATH Open document ID: 0679.05051
DOI: 10.1016/0012-365X(89)90303-8
author: Paul A. Catlin
published in: Discrete Mathematics
publication date: 1989-01-01T00:00:00Z
review text: For a graph G and a connected subgraph H, the contraction G/H is obtained from G by contracting the vertices of H to a single vertex and deleting the arising loops, of course, with preserving all edges between H and G-H inclusive of multiple edges which may arise. If \(M_ 3\) is a matching in G consisting of three independent edges, let \(S(M_ 3)\) denote the sum of the degrees of the six end-vertices of \(M_ 3\) in G. A graph G is collapsible iff for every even set \(T\subseteq V(G)\), there is a subgraph H in G such that G-E(H) is connected and T is the set of vertices of odd degree in H. Now the main result is: If for a 2-edge-connected simple graph G of order n, every 3-matching \(M_ 3\) of G fulfills \(S(M_ 3)\geq 2n+2\) then it holds that either G is collapsible, or \(G/H=K_{2,t}\) for some \(t\geq 2\) and some subgraph H being collapsible or isomorphic to \(K_ 2\), or G is the Cartesian sum of \(K_ 2\) and a path of length 2 (i.e., in a less detailed formulation: Either G has a spanning Eulerian subgraph or \(G/H=K_{2,t}\) for some odd \(t>1\) and some connected subgraph H of G). This result is best-possible with respect to the inequality for \(S(M_ 3)\). Several previous results due to various authors are proved special cases.
Mathematics Subject Classification ID: 05C45
Mathematics Subject Classification ID: 05C70
zbMATH DE Number: 4112639
zbMATH Keywords: graph
zbMATH Keywords: contraction
zbMATH Keywords: matching
zbMATH Keywords: spanning Eulerian subgraph
reviewed by: Günter Schaar
MaRDI profile type: Publication
cites work: Q3757937
cites work: On circuits and pancyclic line graphs
cites work: Q5422499
cites work: Hamiltonian line graphs
cites work: Spanning trails
cites work: A reduction method to find spanning Eulerian subgraphs
cites work: Contractions of graphs with no spanning Eulerian subgraphs
cites work: On hamiltonian line graphs
cites work: On Spanning and Dominating Circuits in Graphs
cites work: The Factorization of Linear Graphs
cites work: Existence of dominating cycles and paths
cites work: Existence of spanning and dominating trails and circuits
description: scientific article; zbMATH DE number 4112639