Intersections of longest cycles in k-connected graphs

DOI10.1006/JCTB.1997.1802MaRDI QIDQ1386428zbMATH OpenOpenAlexFDO

Authors Guantao Chen, Ronald Gould, Ralph Faudree

Publication date 19 October 1998

Published in Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1006/jctb.1997.1802

zbMATH Keywords

connected graphlongest cycles

Mathematics Subject Classification ID

Paths and cycles (05C38)

Review text

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\).

Recommendations

• scientific article; zbMATH DE number 3875324
• Intersections of largest bonds in \(k\)-connected graphs
• Intersections of cycles in \(k\)-connected graphs
• Largest circuits in matroids
• On the Intersections of Longest Cycles in a Graph

Cites work

• A polynomial algorithm for the max-cut problem on graphs without long odd cycles
• Connectivity of transitive graphs
• Eine Eigenschaft der Atome endlicher Graphen
• Graph theory
• scientific article; zbMATH DE number 3140515 (Why is no real title available?)
• scientific article; zbMATH DE number 3875324 (Why is no real title available?)
• scientific article; zbMATH DE number 863469 (Why is no real title available?)
• scientific article; zbMATH DE number 3019031 (Why is no real title available?)
• Long cycles in vertex-transitive graphs
• Some Theorems on Abstract Graphs

Cited in

(16)

• Intersections of largest bonds in \(k\)-connected graphs
• Improvements on Hippchen's conjecture
• The longest cycle problem is polynomial on interval graphs
• Intersections of cycles in \(k\)-connected graphs
• On deletions of largest bonds in graphs
• Intersection of longest paths in a graph
• Nonempty intersection of longest paths in a graph with a small matching number
• Circumferences of k-connected graphs involving independence numbers
• scientific article; zbMATH DE number 3875324 (Why is no real title available?)
• On longest cycles and strongly linking vertex sets
• Intersections of longest cycles in grid graphs
• On the Intersections of Longest Cycles in a Graph
• Transversals of longest cycles in partial k‐trees and chordal graphs
• On two conjectures about the intersection of longest paths and cycles
• Intersection of cycles and paths in k-connected graphs
• Longest cycles in vertex-transitive and highly connected graphs

This page was built for publication: Intersections of longest cycles in \(k\)-connected graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1386428)