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

Stewart, Iain A.; Thompson, Ben

Exp. Math. 4, No. 1, 41-48 (1995).

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.

MSC:

05C38

Paths and cycles

Keywords:

intersection; longest cycles

Citations:

Zbl 0549.05040

Software:

Mathematica

References:

[1]	Babai L., J. Graph Theory pp 301– (1979) · Zbl 0414.05032 · doi:10.1002/jgt.3190030314
[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) · doi:10.1007/BF01222585
[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 · doi:10.1016/S0021-9800(70)80005-9
[6]	Wolfram S., Mathematica: A System for Doing Mathematics by Computer,, 2. ed. (1991) · Zbl 0671.65002