Transversals of Longest Paths and Cycles
From MaRDI portal
Abstract: Let G be a graph of order n. Let lpt(G) be the minimum cardinality of a set X of vertices of G such that X intersects every longest path of G and define lct(G) analogously for cycles instead of paths. We prove that lpt(G) leq ceiling(n/4-n^{2/3}/90), if G is connected, lct(G) leq ceiling(n/3-n^{2/3}/36), if G is 2-connected, and lpt(G) leq 3, if G is a connected circular arc graph. Our bound on lct(G) improves an earlier result of Thomassen and our bound for circular arc graphs relates to an earlier statement of Balister emph{et al.} the argument of which contains a gap. Furthermore, we prove upper bounds on lpt(G) for planar graphs and graphs of bounded tree-width.
Recommendations
- On relative length of longest paths and cycles
- Intersecting longest paths and longest cycles: a survey
- Transversals of longest cycles in partial k‐trees and chordal graphs
- Long cycles and paths in distance graphs
- Transversals of longest cycles in chordal and bounded tree-width graphs
- Long paths, long cycles, and their relative length
- scientific article; zbMATH DE number 3875324
- scientific article; zbMATH DE number 68340
Cited in
(23)- Gallai's question and constructions of almost hypotraceable graphs
- Reducing graph transversals via edge contractions
- Using edge contractions to reduce the semitotal domination number
- Well-partitioned chordal graphs
- The longest cycle problem is polynomial on interval graphs
- Transversals of longest cycles in chordal and bounded tree-width graphs
- Destroying longest cycles in graphs and digraphs
- A note on longest paths in circular arc graphs
- Intersecting longest paths in chordal graphs
- The complexity of blocking (semi)total dominating sets with edge contractions
- Non-empty intersection of longest paths in H-free graphs
- Three problems on well-partitioned chordal graphs
- Detour trees
- Alternating paths and cycles of minimum length
- Sublinear longest path transversals
- Reducing graph transversals via edge contractions
- Intersection of longest paths in graph classes
- Intersection of longest paths in graph classes
- Transversals of longest cycles in partial k‐trees and chordal graphs
- Improved upper bounds on longest-path and maximal-subdivision transversals
- Bonds Intersecting Long Paths in \(k\) -Connected Graphs
- Longest cycles in vertex-transitive and highly connected graphs
- Small hitting sets for longest paths and cycles
This page was built for publication: Transversals of Longest Paths and Cycles
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4979843)
