Nonempty intersection of longest paths in series-parallel graphs
From MaRDI portal
Publication:729758
Abstract: In 1966 Gallai asked whether all longest paths in a connected graph have nonempty intersection. This is not true in general and various counterexamples have been found. However, the answer to Gallai's question is positive for several well-known classes of graphs, as for instance connected outerplanar graphs, connected split graphs, and 2-trees. A graph is series-parallel if it does not contain as a minor. Series-parallel graphs are also known as partial 2-trees, which are arbitrary subgraphs of 2-trees. We present a proof that every connected series-parallel graph has a vertex that is common to all of its longest paths. Since 2-trees are maximal series-parallel graphs, and outerplanar graphs are also series-parallel, our result captures these two classes in one proof and strengthens them to a larger class of graphs. We also describe how this vertex can be found in linear time.
Recommendations
Cites work
- A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
- Counting \(H-\)colorings of partial \(k-\)trees
- Graph Classes: A Survey
- Graph theory
- Graph theory. Foreword by Crispin St. J. A. Nash-Williams.
- HAMILTONian circuits in chordal bipartite graphs
- scientific article; zbMATH DE number 2134119 (Why is no real title available?)
- scientific article; zbMATH DE number 4174966 (Why is no real title available?)
- scientific article; zbMATH DE number 5294801 (Why is no real title available?)
- scientific article; zbMATH DE number 49078 (Why is no real title available?)
- scientific article; zbMATH DE number 487720 (Why is no real title available?)
- scientific article; zbMATH DE number 4121424 (Why is no real title available?)
- scientific article; zbMATH DE number 3451870 (Why is no real title available?)
- scientific article; zbMATH DE number 3248752 (Why is no real title available?)
- Intersecting longest paths
- Intersecting longest paths and longest cycles: a survey
- Linear time algorithms for NP-hard problems restricted to partial k- trees
- Longest Paths in Circular Arc Graphs
- On Linear Time Minor Tests with Depth-First Search
- On longest paths and circuits in graphs.
- On longest paths in triangular lattice graphs
- Planar and infinite hypohamiltonian and hypotraceable graphs
- Research problems
- Smallest sets of longest paths with empty intersection
- The longest path problem is polynomial on cocomparability graphs
- Vertices missed by longest paths or circuits
- WHEN DO THREE LONGEST PATHS HAVE A COMMON VERTEX?
- Über die Nichtexistenz eines Knotenpunktes, durch den alle längsten Wege eines Graphen gehen
- Über längste Wege und Kreise in Graphen
Cited in
(23)- Nonempty intersection of longest paths in \(2K_2\)-free graphs
- Gallai's question and constructions of almost hypotraceable graphs
- Reducing graph transversals via edge contractions
- Using edge contractions to reduce the semitotal domination number
- \(\alpha\)-diperfect digraphs
- Well-partitioned chordal graphs
- Improvements on Hippchen's conjecture
- Nonempty intersection of longest paths in graphs without forbidden pairs
- 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
- Nonempty intersection of longest paths in a graph with a small matching number
- Order of the smallest counterexample to Gallai's conjecture
- Reducing graph transversals via edge contractions
- Intersection of longest paths in graph classes
- All longest cycles in a 2‐connected partial 3‐tree share a common vertex
- Bonds Intersecting Long Paths in \(k\) -Connected Graphs
- Measuring the distance to series-parallelity by path expressions
- A (1/2+1/60)-approximation algorithm for maximum weight series-parallel subgraph
- Longest path transversals in claw-free and P₅-free graphs
- Longest cycles in vertex-transitive and highly connected graphs
- Small hitting sets for longest paths and cycles
This page was built for publication: Nonempty intersection of longest paths in series-parallel graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q729758)
