On a question of van Aardt et al. on destroying all longest cycles. (English) Zbl 1409.05119

Summary: 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 S. A. van Aardt et al. [Discrete Appl. Math. 186, 251–259 (2015; Zbl 1311.05094)] 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.


05C38 Paths and cycles
05C12 Distance in graphs
05C35 Extremal problems in graph theory
05C40 Connectivity


Zbl 1311.05094
Full Text: DOI


[1] Aldred, R.E.L., McKay, B.D., Wormald, N.C.: Small hypohamiltonian graphs. J. Combin. Math. Combin. Comput. 23, 143-152 (1997) · Zbl 0880.05061
[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) · Zbl 1306.05121 · doi:10.5614/ejgta.2013.1.1.6
[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) · Zbl 0371.05015
[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) · Zbl 1311.05094 · doi:10.1016/j.dam.2015.01.010
[5] Zamfirescu, C.T.: On non-hamiltonian graphs for which every vertex-deleted subgraph is traceable. J. Graph Theory 86, 223-243 (2017) · Zbl 1370.05115 · doi:10.1002/jgt.22122
[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) · Zbl 1393.05095 · doi:10.1002/jgt.22228
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.