Skip to main content
SpringerLink
Log in

On Sufficient Conditions for Hamiltonicity in Dense Graphs

  • Conference paper
  • First Online:
Extended Abstracts EuroComb 2021

Part of the book series: Trends in Mathematics ((RPCRMB,volume 14))

  • 1141 Accesses

Abstract

We study structural conditions in dense graphs that guarantee the existence of vertex-spanning substructures such as Hamilton cycles. Recall that every Hamiltonian graph is connected, has an almost perfect matching and, excluding the bipartite case, contains an odd cycle. Our main result states that any large enough graph that robustly satisfies these properties must already be Hamiltonian. Moreover, the same holds for powers of cycles and the bandwidth setting subject to natural generalizations of connectivity, matchings and odd cycles.

This solves the embedding problem that underlies multiple lines of research on sufficient conditions for Hamiltonicity. As an application, we recover several old and new results, and prove versions of the Bandwidth Theorem under Ore-type degree conditions, Pósa-type degree conditions, deficiency-type conditions and for balanced partite graphs.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution
Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 149.00
Price excludes VAT (USA)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 199.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Notes

  1. 1.

    Indeed, a quick exercise shows that every graph satisfying the conditions of Ore’s theorem also satisfies the conditions of Pósa’s theorem.

References

  1. Balogh, J., Kostochka, A.V., Treglown, A.: On perfect packings in dense graphs, arXiv:1110.3490 (2011)

  2. Balogh, J., Kostochka, A.V., Treglown, A: On perfect packings in dense graphs. Electron. J. Combin. 20(1), Paper 57, 17 (2013)

    Google Scholar 

  3. Böttcher, J., Schacht, M., Taraz, A.: Proof of the bandwidth conjecture of Bollobás and Komlós. Math. Ann. 343(1), 175–205 (2009)

    Article  MathSciNet  Google Scholar 

  4. Châu, P.: An Ore-type theorem on Hamiltonian square cycles. Graph. Combinator. 29(4), 795–834 (2013)

    Article  MathSciNet  Google Scholar 

  5. Ebsen, O., Maesaka, G., Reiher, C., Schacht, M., Schülke, B.: Embedding spanning subgraphs in uniformly dense and inseparable graphs. Random Struct. Algorithms 57(4), 1077–1096 (2020)

    Article  MathSciNet  Google Scholar 

  6. Freschi, A., Hyde, J., Treglown, A.: On deficiency problems for graphs, arXiv:2102.04389 (2021)

  7. Gould, R.J.: Recent advances on the Hamiltonian problem: survey III. Graphs Comb. 30(1), 1–46 (2014)

    Article  MathSciNet  Google Scholar 

  8. Hajnal, A., Szemerédi, E.: Proof of a conjecture of P. Erdős. Combinatorial theory and its applications, II (Proc. Colloq., Balatonfüred, 1969), pp. 601–623 (1970)

    Google Scholar 

  9. Kierstead, H.A., Kostochka, A.V.: An Ore-type theorem on equitable coloring. J. Combin. Theory Ser. B 98(1), 226–234 (2008)

    Article  MathSciNet  Google Scholar 

  10. Keevash, P., Mycroft, R.: A multipartite Hajnal-Szemerédi theorem. J. Combin. Theory Ser. B 114, 187–236 (2015)

    Article  MathSciNet  Google Scholar 

  11. Knox, F., Treglown, A.: Embedding spanning bipartite graphs of small bandwidth. Comb. Probab. Comput. 22(1), 71–96 (2013)

    Article  MathSciNet  Google Scholar 

  12. Komlós, J., Sárközy, G.N., Szemerédi, E.: On the square of a Hamiltonian cycle in dense graphs. In: Proceedings of the Seventh International Conference on Random Structures and Algorithms (Atlanta, GA, 1995), vol. 9, pp. 193–211 (1996)

    Google Scholar 

  13. Komlós, J., Sárközy, G.N., Szemerédi, E.: On the Pósa-Seymour conjecture. J. Graph Theory 29(3), 167–176 (1998)

    Article  MathSciNet  Google Scholar 

  14. Komlós, J., Sárközy, G.N., Szemerédi, E.: Proof of the Seymour conjecture for large graphs. Ann. Comb. 2(1), 43–60 (1998)

    Article  MathSciNet  Google Scholar 

  15. Kühn, D., Osthus, D.: Hamilton cycles in graphs and hypergraphs: an extremal perspective. In: Proceedings of ICM 2014 (Seoul, Korea), vol. 4, pp. 381–406 (2014)

    Google Scholar 

  16. Nenadov, R., Sudakov, B., Wagner, A.Z.: Completion and deficiency problems. J. Comb. Theory Ser. B 145, 214–240 (2020)

    Article  MathSciNet  Google Scholar 

  17. Staden, K., Treglown, A.: On degree sequences forcing the square of a Hamilton cycle. SIAM J. Discret. Math. 31(1), 383–437 (2017)

    Article  MathSciNet  Google Scholar 

  18. Staden, K., Treglown, A.: The bandwidth theorem for locally dense graphs. In: Forum Mathematics Sigma, vol. 8, p. 42 (2020)

    Google Scholar 

  19. Treglown, A.: A degree sequence Hajnal-Szemerédi theorem. J. Combin. Theory Ser. B 118, 13–43 (2016)

    Article  MathSciNet  Google Scholar 

  20. Treglown, A.: Personal communication (2020)

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Universität Heidelberg, Heidelberg, Germany

    Richard Lang

  2. Czech Academy of Sciences, Prague, Czechia

    Nicolás Sanhueza-Matamala

Authors
  1. Richard Lang
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Nicolás Sanhueza-Matamala
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. Computer Science Institute, Charles University, Praha, Czech Republic

    Jaroslav Nešetřil

  2. Departament de Matemàtiques, Universitat Politècnica de Catalunya, Barcelona, Spain

    Guillem Perarnau

  3. Departament de Matemàtiques, Universitat Politècnica de Catalunya, Castelldefels, Spain

    Juanjo Rué

  4. Departament de Matemàtiques, Universitat Politècnica de Catalunya, Barcelona, Spain

    Oriol Serra

Rights and permissions

Reprints and permissions

Copyright information

© 2021 The Author(s), under exclusive license to Springer Nature Switzerland AG

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Lang, R., Sanhueza-Matamala, N. (2021). On Sufficient Conditions for Hamiltonicity in Dense Graphs. In: Nešetřil, J., Perarnau, G., Rué, J., Serra, O. (eds) Extended Abstracts EuroComb 2021. Trends in Mathematics(), vol 14. Birkhäuser, Cham. https://doi.org/10.1007/978-3-030-83823-2_85

Download citation

Publish with us

Policies and ethics

Search

Navigation