Intersections of longest cycles in \(k\)-connected graphs (Q1386428)
From MaRDI portal
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Intersections of longest cycles in \(k\)-connected graphs |
scientific article |
Statements
Intersections of longest cycles in \(k\)-connected graphs (English)
0 references
19 October 1998
0 references
Let \(G\) be a connected graph, where \(k\geq 2\). S. Smith conjectured that every two longest cycles of \(G\) have at least \(k\) vertices in common. We show that every two longest cycles meet in at least \(ck^{3/5}\) vertices, where \(c\approx 0.2615\).
0 references
connected graph
0 references
longest cycles
0 references
