Spanning Eulerian subgraphs and matchings (Q1124608)

From MaRDI portal
scientific article
Language Label Description Also known as
English
Spanning Eulerian subgraphs and matchings
scientific article

    Statements

    Spanning Eulerian subgraphs and matchings (English)
    0 references
    0 references
    1989
    0 references
    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.
    0 references
    graph
    0 references
    contraction
    0 references
    matching
    0 references
    spanning Eulerian subgraph
    0 references

    Identifiers