Spanning trails avoiding and containing given edges

Lei, Lan ; Li, Xiaomin ; Song, Sulin  ; Xie, Yikang ; Lai, Hong-Jian

Discussiones Mathematicae. Graph Theory, Tome 44 (2024) no. 4, pp. 1429-1447

Résumé

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).

Détail

Keywords: $\alpha$-permutation graph, $(s, t)$-supereulerian, edge connectivity, collapsible graph