Article in press
Authors:
Lan Lei
School of Mathematics and Statistics, Chongqing Technology and Business University, Chongqing 400067
email: leilan@ctbu.edu.cn
Yikang Xie
School of Mathematics and Statistics, Jiangxi Normal University, Nanchang 330000
email: yx0010@mix.wvu.edu
Hong-Jian Lai
Department of Mathematics, West Virginia University, Morgantown, WV 26506
email: hjlai@math.wvu.edu
Title:
Spanning trails avoiding and containing given edges
PDFSource:
Discussiones Mathematicae Graph Theory
Received: 2022-10-21 , Revised: 2023-06-06 , Accepted: 2023-06-06 , Available online: 2023-07-19 , https://doi.org/10.7151/dmgt.2505
Abstract:
Let $\kappa'(G)$ denote the edge connectivity of a graph $G$. For any disjoint
subsets $X,Y \subseteq E(G)$ with $|Y|\le \kappa'(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|\le \kappa'(G)$. These results are applied to show
that if $G$ is $(s,t)$-supereulerian (that is, for any disjoint
subsets $X, Y \subseteq E(G)$ with $|X| \le s$ and $|Y| \le t$,
$G$ has a spanning closed trail that contains $X$ and avoids $Y$) with
$\kappa'(G)=\delta(G)\ge 3$, then for any permutation $\alpha$ on the vertex
set $V(G)$, the permutation graph $\alpha(G)$ is $(s,t)$-supereulerian if and
only if $s+t\le \kappa'(G)$.
Keywords:
$\alpha$-permutation graph, $(s, t)$-supereulerian, edge connectivity, collapsible graph
References:
- 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 - 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 - 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 - 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 - A.J. Bondy and U.S.R. Murty, Graph Theory with Applications (American Elsevier, 1976).
- 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 - P.A. Catlin, Supereulerian graphs: A survey, J. Graph Theory 16 (1992) 177–196.
https://doi.org/10.1002/jgt.3190160209 - 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 - 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 - 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.
- G. Chartrand and F. Harary, Planar permutation graphs, Ann. Inst. Henri Poincaré Probab. Stat. 3 (1967) 433–438.
- 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.
- M.R. Garey and D.S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness (W.H. Freeman and Company, 1979).
- 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 - A.M. Hobbs, Network survivability, in: Appl. Discrete Math., J.G. Michaels and K.H. Rosen (Ed(s)), (McGraw-Hill 1991) 332–353.
- 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 - H.-J. Lai, Y. Shao and H. Yan, An update on supereulerian graphs, WSEAS Transactions on Mathematics 12 (2013) 926–940.
- 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.
- 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.
- 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 - 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 - 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 - 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 - R.D. Ringeisen, On cycle permutation graphs, Discrete Math. 51 (1984) 265–275.
https://doi.org/10.1016/0012-365X(84)90007-4 - 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 - X. Zhu, A hypercube variant with small diameter, J. Graph Theory 85 (2017) 651–660.
https://doi.org/10.1002/jgt.22096
Close