Geodesic
Spanning trails avoiding and containing given edges
Discussiones Mathematicae. Graph Theory, Tome 44 (2024) no. 4, pp. 1429-1447 Cet article a éte moissonné depuis la source Library of Science

Voir la notice de l'article

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).
Keywords: $\alpha$-permutation graph, $(s, t)$-supereulerian, edge connectivity, collapsible graph 
@article{DMGT_2024_44_4_a10,
     author = {Lei, Lan and Li, Xiaomin and Song, Sulin and Xie, Yikang and Lai, Hong-Jian},
     title = {Spanning trails avoiding and containing given edges},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {1429--1447},
     year = {2024},
     volume = {44},
     number = {4},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2024_44_4_a10/}
}
TY  - JOUR
AU  - Lei, Lan
AU  - Li, Xiaomin
AU  - Song, Sulin
AU  - Xie, Yikang
AU  - Lai, Hong-Jian
TI  - Spanning trails avoiding and containing given edges
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2024
SP  - 1429
EP  - 1447
VL  - 44
IS  - 4
UR  - http://geodesic.mathdoc.fr/item/DMGT_2024_44_4_a10/
LA  - en
ID  - DMGT_2024_44_4_a10
ER  - 
%0 Journal Article
%A Lei, Lan
%A Li, Xiaomin
%A Song, Sulin
%A Xie, Yikang
%A Lai, Hong-Jian
%T Spanning trails avoiding and containing given edges
%J Discussiones Mathematicae. Graph Theory
%D 2024
%P 1429-1447
%V 44
%N 4
%U http://geodesic.mathdoc.fr/item/DMGT_2024_44_4_a10/
%G en
%F DMGT_2024_44_4_a10
Lei, Lan; Li, Xiaomin; Song, Sulin; Xie, Yikang; Lai, Hong-Jian. Spanning trails avoiding and containing given edges. Discussiones Mathematicae. Graph Theory, Tome 44 (2024) no. 4, pp. 1429-1447. http://geodesic.mathdoc.fr/item/DMGT_2024_44_4_a10/

[1] C. Balbuena, X. Marcote and P. García-Vázquez, On restricted connectivities of permutation graphs, Networks 45 (2005) 113–118. https://doi.org/10.1002/net.20056

[2] C. Balbuena, P. García-Vázquez and X. Marcote, Reliability of interconnection networks modelled by a product of graphs, Networks 48 (2006) 114–120. https://doi.org/10.1002/net.20124

[3] J.C. Bermond, C. Delorme and G. Farhi, Large graphs with given degree and diameter II}, J. Combin. Theory Ser. B 36 (1984) 32–84. https://doi.org/10.1016/0095-8956(84)90012-1

[4] F.T. Boesch, C. Suffel and R. Tindell, The spanning subgraphs of eulerian graphs, J. Graph Theory 1 (1977) 79–84. https://doi.org/10.1002/jgt.3190010115

[5] A.J. Bondy and U.S.R. Murty, Graph Theory with Applications (American Elsevier, 1976).

[6] P.A. Catlin, A reduction method to find spanning Eulerian subgraphs, J. Graph Theory 12 (1988) 29–44. https://doi.org/10.1002/jgt.3190120105

[7] P.A. Catlin, Supereulerian graphs: A survey, J. Graph Theory 16 (1992) 177–196. https://doi.org/10.1002/jgt.3190160209

[8] P.A. Catlin, Z.-Y. Han and H.-J. Lai, Graphs without spanning closed trails, Discrete Math. 160 (1996) 81–91. https://doi.org/10.1016/S0012-365X(95)00149-Q

[9] P.A. Catlin, T. Iqbalunnisa, T.N. Janakiraman and N. Srinivasan, Hamilton cycles and closed trails in iterated line graphs, J. Graph Theory 14 (1990) 347–364. https://doi.org/10.1002/jgt.3190140308

[10] G. Chartrand and J. Frechen, On the chromatic number of permutation graphs, in: Proof Techniques in Graph Theory, Proceedings of the Second Ann Arbor Graph Theory Conference, F. Harary (Ed(s)), (Academic Press, New York, London 1969) 21–24.

[11] G. Chartrand and F. Harary, Planar permutation graphs, Ann. Inst. Henri Poincaré Probab. Stat. 3 (1967) 433–438.

[12] Z.H. Chen and H.-J. Lai, Reduction techniques for supereulerian graphs and related topics–-a survey, in: Combinatorics and Graph Theory'95, T.-H. Gu (Ed(s)), (World Sci. Pub. River Edge N.J. 1995) 53–69.

[13] M.R. Garey and D.S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness (W.H. Freeman and Company, 1979).

[14] R. Gu, H.-J. Lai, Y. Liang, Z. Miao and M. Zhang, Collapsible subgraphs of a 4-edge-connected graph, Discrete Appl. Math. 260 (2019) 272–277. https://doi.org/10.1016/j.dam.2019.01.033

[15] A.M. Hobbs, Network survivability, in: Appl. Discrete Math., J.G. Michaels and K.H. Rosen (Ed(s)), (McGraw-Hill 1991) 332–353.

[16] H.-J. Lai, Large survivable nets and the generalized prisms, Discrete Appl. Math. 61 (1995) 181–185. https://doi.org/10.1016/0166-218X(94)00131-V

[17] H.-J. Lai, Y. Shao and H. Yan, An update on supereulerian graphs, WSEAS Transactions on Mathematics 12 (2013) 926–940.

[18] L. Lei, X. Li and B. Wang, On (s,t)-supereulerian locally connected graphs, in: International Conference on Computational Science, Y. Shi, G.D. Albada, J. Dongarra and P.M.A. Sloot (Ed(s)), (Springer 2007) 384–388.

[19] L. Lei and X. Li, A note on the connectivity of generalized prisms, J. Southwest China Normal University (Natural Science Edition) 33 (2008) 1–3.

[20] L. Lei, X. Li, B. Wang and H.-J. Lai, On (s,t)-supereulerian graphs in locally highly connected graphs, Discrete Math. 310 (2010) 929–934. https://doi.org/10.1016/j.disc.2009.08.012

[21] X. Li, L. Lei and H.-J. Lai, The connectivity of generalized graph products, Inform. Process. Lett. 136 (2018) 37–40. https://doi.org/10.1016/j.ipl.2018.03.014

[22] B.L. Piazza and R.D. Ringeisen, Connectivity of generalized prisms over G, Discrete Appl. Math. 30 (1991) 229–233. https://doi.org/10.1016/0166-218X(91)90047-Z

[23] W.R. Pulleyblank, A note on graphs spanned by Eulerian graphs, J. Graph Theory 3 (1979) 309–310. https://doi.org/10.1002/jgt.3190030316

[24] R.D. Ringeisen, On cycle permutation graphs, Discrete Math. 51 (1984) 265–275. https://doi.org/10.1016/0012-365X(84)90007-4

[25] W. Xiong, S. Song and H.-J. Lai, Polynomially determine if a graph is (s,3)-supereulerian, Discrete Math. 344(12) (2021) 112601. https://doi.org/10.1016/j.disc.2021.112601

[26] X. Zhu, A hypercube variant with small diameter, J. Graph Theory 85 (2017) 651–660. https://doi.org/10.1002/jgt.22096