On the intersections of longest cycles in a graph
Stewart, Iain A. ; Thompson, Ben
Experiment. Math., Tome 4 (1995) no. 4, p. 41-48 / Harvested from Project Euclid
We confirm a conjecture, due to Grötschel, regarding the intersection vertices of two longest cycles in a graph. 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
Publié le : 1995-05-14
Classification:  05C38
@article{1062621141,
     author = {Stewart, Iain A. and Thompson, Ben},
     title = {On the intersections of longest cycles in a graph},
     journal = {Experiment. Math.},
     volume = {4},
     number = {4},
     year = {1995},
     pages = { 41-48},
     language = {en},
     url = {http://dml.mathdoc.fr/item/1062621141}
}
Stewart, Iain A.; Thompson, Ben. On the intersections of longest cycles in a graph. Experiment. Math., Tome 4 (1995) no. 4, pp.  41-48. http://gdmltest.u-ga.fr/item/1062621141/