##
**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.

### MSC:

05C38 | Paths and cycles |

### Citations:

Zbl 0549.05040### Software:

Mathematica
PDF
BibTeX
XML
Cite

\textit{I. A. Stewart} and \textit{B. Thompson}, Exp. Math. 4, No. 1, 41--48 (1995; Zbl 0841.05056)

### References:

[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.