Spanning Eulerian subgraphs and matchings

Eulerian and Hamiltonian graphs (05C45) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

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.

Recommendations

Cites work

Cited in

(15)

This page was built for publication: Spanning Eulerian subgraphs and matchings

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1124608)