Supereulerian graphs and excluded induced minors (Q1903724): Difference between revisions

A graph is supereulerian if it has a spanning eulerian subgraph. A wheel is the graph obtained from an \(n\)-cycle \(v_1, v_2,\dots, v_n, v_1\), where \(n\geq 2\), by joining a new vertex \(v\) to every vertex on the cycle. The subdivided wheel \(W^*_n\) is obtained from \(W_n\) by replacing each edge \(v_i v_{i+ 1}\) by a path \(v_i, v_i', v_{i+ 1}\) of length 2, where \(\{v_1',\dots, v_n'\}\cap V(W_n)= \varnothing\). Let \({\mathcal W}= \{W^*_n\mid n\geq 2\}\). For a subgraph \(H\) of \(G\), the contraction \(G/H\) is the graph obtained from \(G\) by identifying the ends of each edge in \(H\) and deleting resulting loops. A graph \(M\) is an induced minor of \(G\) if \(M\) is isomorphic to a contraction of an induced subgraph of \(G\). In the main result of this paper it is shown that if \(G\) is 2-edge-connected, then every 2-edge-connected induced subgraph of \(G\) is supereulerian if and only if \(G\) has no induced minor isomorphic to a member of \(\mathcal W\).