Spanning trails avoiding and containing given edges
Lan Lei, Xiaomin Li, Sulin Song, Yikang Xie, Hong‐Jian Lai · Discussiones Mathematicae Graph Theory · 2023
Let κ (G) denote the edge connectivity of a graph G.For any disjoint subsets X, Y ⊆ E(G) with |Y | ≤ κ (G) -1, a necessary and sufficient condition for G -Y to be a contractible configuration for G containing a spanning closed trail is obtained.We also characterize the structure of a graph G that has a spanning closed trail containing X and avoiding Y when |X| + |Y | ≤ κ (G).These results are applied to show that if G is (s, t)supereulerian (that is, for any disjoint subsets X, Y ⊆ E(G) with |X| ≤ s and |Y | ≤ t, G has a spanning closed trail that contains X and avoids Y ) with κ (G) = δ(G) ≥ 3, then for any permutation α on the vertex set V (G), the permutation graph α(G) is (s, t)-supereulerian if and only if s+t ≤ κ (G).