On the intersections of longest cycles in a graph. (English) Zbl 0841.05056

Summary: We confirm a conjecture, due to Grötschel, regarding the intersection vertices of two longest cycles in a graph; see M. Grötschel [Graph theory and combinatorics, Proc. Conf. Hon. P. Erdös, Cambridge 1983, 171-189 (1984; Zbl 0549.05040)]. In particular, we show that if \(G\) is a graph of circumference at least \(k+ 1\), where \(k\in \{6, 7\}\), and \(G\) has two longest cycles meeting in a set \(W\) of \(k\) vertices, then \(W\) is an articulation set. Grötschel had previously proved this result for \(k\in \{3, 4, 5\}\) and shown that it fails for \(k> 7\). As corollaries, we obtain results regarding the minimum lengths of longest cycles in certain vertex-transitive graphs. Our proofs are novel in that they make extensive use of a computer, although the programs themselves are straightforward.


05C38 Paths and cycles


Zbl 0549.05040


Full Text: DOI Euclid EuDML EMIS


[1] Babai L., J. Graph Theory pp 301– (1979) · Zbl 0414.05032
[2] Grötschel, M. ”On intersections of longest cycles’. Graph Theory and Combinatorics: Proceedings of the Cambridge Combinatorial Conference in Honour of Paul Erdös. Edited by: Bollobás, B. pp.171–189. London: Academic Press. [Grötschel 1984]
[3] Mader W., Arch. Math. (Basel) 22 pp 333– (1971)
[4] Stewart I. A., ”On the intersections of longest cycles in a graph’ (1994)
[5] Watkins M. E., J. Combinat. Theory pp 23– (1970) · Zbl 0185.51702
[6] Wolfram S., Mathematica: A System for Doing Mathematics by Computer,, 2. ed. (1991) · Zbl 0671.65002
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.