Skip to main content
SpringerLink
Log in

On a Question of van Aardt et al. on Destroying All Longest Cycles

  • Original Paper
  • Published:
Graphs and Combinatorics Aims and scope Submit manuscript

Abstract

We describe an infinite family of 2-connected graphs, each of which has the property that the intersection of all longest cycles is empty. In particular, we present such graphs with circumference 10, 13, and 16. This settles a question of van Aardt et al. (Discrete Appl Math 186:251–259, 2015) concerning the existence of such graphs for all but one case, namely circumference 11. We also present a 2-connected graph of circumference 11 in which all but one vertex are avoided by some longest cycle.

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

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1

Similar content being viewed by others

References

  1. Aldred, R.E.L., McKay, B.D., Wormald, N.C.: Small hypohamiltonian graphs. J. Combin. Math. Combin. Comput. 23, 143–152 (1997)

    MathSciNet  MATH  Google Scholar 

  2. Shabbir, A., Zamfirescu, C.T., Zamfirescu, T.I.: Intersecting longest paths and longest cycles: a survey. Electron. J. Graph Theory Appl. 1, 56–76 (2013)

    Article  MathSciNet  MATH  Google Scholar 

  3. Thomassen, C.: Hypohamiltonian graphs and digraphs. In: Proc. Internat. Conf. Theory and Appl. of Graphs, Kalamazoo, 1976, LNCS 642, Springer, Berlin 557–571 (1978)

  4. van Aardt, S.A., Burger, A.P., Dunbar, J.E., Frick, M., Llano, B., Thomassen, C., Zuazua, R.: Destroying longest cycles in graphs and digraphs. Discrete Appl. Math. 186, 251–259 (2015)

    Article  MathSciNet  MATH  Google Scholar 

  5. Zamfirescu, C.T.: On non-hamiltonian graphs for which every vertex-deleted subgraph is traceable. J. Graph Theory 86, 223–243 (2017)

    Article  MathSciNet  MATH  Google Scholar 

  6. Zamfirescu, C.T., Zamfirescu, T.I.: Every graph occurs as an induced subgraph of some hypohamiltonian graph. J. Graph Theory 88, 551–557 (2018)

    Article  MathSciNet  MATH  Google Scholar 

Download references

Acknowledgements

This research was supported by a Postdoctoral Fellowship of the Research Foundation Flanders (FWO).

Author information

Authors and Affiliations

  1. Department of Applied Mathematics, Computer Science and Statistics, Ghent University, Krijgslaan 281-S9, 9000, Ghent, Belgium

    Carol T. Zamfirescu

  2. Department of Mathematics, Babeş-Bolyai University, Cluj-Napoca, Romania

    Carol T. Zamfirescu

Authors
  1. Carol T. Zamfirescu
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Carol T. Zamfirescu.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Zamfirescu, C.T. On a Question of van Aardt et al. on Destroying All Longest Cycles. Graphs and Combinatorics 35, 479–483 (2019). https://doi.org/10.1007/s00373-019-02010-9

Download citation

  • Received:

  • Revised:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00373-019-02010-9

Keywords

Mathematics Subject Classification

Search

Navigation