Spanning Trails with Maximum Degree at Most 4 in \(2K_2\)-Free Graphs

1. Bauer, D., Broersma, H.J., Veldman, H.J.: Not every 2-tough graph is Hamiltonian. In: Proceedings of the 5th Twente Workshop on Graphs and Combinatorial Optimization (Enschede, 1997), vol. 99, pp. 317–321 (2000)

2. Bauer, D., Broersma, H.J., Schmeichel, E.: Toughness in graphs—a survey. Graphs Combin. 22(1), 1–35 (2006)

   Article  MATH  MathSciNet  Google Scholar 

3. Broersma, H., Patel, V., Pyatkin, A.: On toughness and Hamiltonicity of \(2K_2\)-free graphs. J. Graph Theory 75(3), 244–255 (2014)

   Article  MATH  MathSciNet  Google Scholar 

4. Chung, F.R.K., Gyárfás, A., Tuza, Z., Trotter, W.T.: The maximum number of edges in \(2K_2\)-free graphs of bounded degree. Discrete Math. 81(2), 129–135 (1990)

   Article  MATH  MathSciNet  Google Scholar 

5. Chvátal, V.: Tough graphs and Hamiltonian circuits. Discrete Math. 5, 215–228 (1973)

   Article  MATH  MathSciNet  Google Scholar 

6. El-Zahar, M., Erdős, P.: On the existence of two nonneighboring subgraphs in a graph. Combinatorica 5(4), 295–300 (1985)

   Article  MATH  MathSciNet  Google Scholar 

7. Ellingham, M.N., Zha, X., Zhang, Y.: Spanning 2-trails from degree sum conditions. J. Graph Theory 45(4), 298–319 (2004)

   Article  MATH  MathSciNet  Google Scholar 

8. Gao, M., Pasechnik, D.: On \(k\)-walks in \(2{K}_2\)-free graphs. (2014) arXiv:1412.0514v2

9. Gao, M., Pasechnik, D.: Edge-dominating cycles, \(k\)-walks and hamilton prisms in \(2{K}_2\)-free graphs. J. Knot Theory Ramif 25(12), 1642011.1–1642011.9 (2016)

   MATH  Google Scholar 

10. Jackson, B ., Wormald, N .C.: \(k\)-walks of graphs. Australas. J. Combin 2, 135–146 (1990). Combinatorial mathematics and combinatorial computing, vol. 2 (Brisbane, 1989)

11. Li, Ping, Li, Hao, Chen, Ye, Fleischner, Herbert, Lai, Hong-Jian: Supereulerian graphs with width \(s\) and \(s\)-collapsible graphs. Discrete Appl. Math. 200, 79–94 (2016)

    Article  MATH  MathSciNet  Google Scholar 

12. Meister, D.: Two characterisations of minimal triangulations of \(2K_2\)-free graphs. Discrete Math. 306(24), 3327–3333 (2006)

    Article  MATH  MathSciNet  Google Scholar 

13. Paoli, M., Peck, G.W., Trotter Jr., W.T., West, D.B.: Large regular graphs with no induced \(2K_2\). Graphs Combin. 8(2), 165–197 (1992)

    Article  MATH  MathSciNet  Google Scholar 

Download references