Edge-Connectivities for Spanning Trails with Prescribed Edges

Abstract

For a graph \(G\), a \({trail}\) is a vertex-edge alternating sequence \(v_0, e_1, v_1, e_2, \ldots, e_{k-1},v_{k-1}, e_k, v_k\) such that all \(e_i\)’s are distinct and \(e_i = v_{i-1}v_i\) for all \(i\). For \(u, v \in V(G)\), a \((u,v)\)-trail of \(G\) is a trail in \(G\) originating at \(u\) and terminating at \(v\). A closed trail is a \((u,v)\)-trail with \(u = v\). A trail \(H\) is a spanning trail of \(G\) if \(V(H) = V(G)\). Let \(X \subseteq E(G)\) and \(Y \subseteq E(G)\) with \(X \cap Y = \emptyset\). This paper studies the minimum edge-connectivity of \(G\) such that for any \(u, v \in V(G)\) (including \(u = v\)), \(G\) has a spanning \((u, v)\)-trail \(H\) with \(X \subseteq E(H)\) and \(Y \cap E(H) = \emptyset\).