Spanning trails containing given edges (Q817757)

Let \(r\geq 0\) be an integer. A graph \(G\) is called \(r\)-Eulerian-connected if for any \(X\subseteq E(G)\) with \(| X| \leq r\) and for any two vertices \(u,v\in V(G)\) (including the case \(u=v\)), the graph \(G\) has a spanning \((u,v)\)-trail containing all edges of \(X\), and \(G\) is called \(r\)-edge-Eulerian-connected if for any \(X\subseteq E(G)\) with \(| X| \leq r\) and for any two different edges \(e',e''\in E(G)\), the graph \(G\) has a spanning \((e',e'')\)-trail containing all edges of \(X\). Let \(\theta(r)\) be the minimum value of \(k\) such that each \(k\)-edge-connected graph is \(r\)-Eulerian-connected. Catlin proved that \(\theta(0)=4\). In this paper the authors show that \(\theta(r)=4\) for \(0\leq r\leq 2\) and \(\theta(r)=r+1\) for \(r\geq 3\). Results on \(r\)-edge-Eulerian-connected graphs are also presented.