Nonempty intersection of longest paths in series-parallel graphs
From MaRDI portal
Publication:729758
DOI10.1016/j.disc.2016.07.023zbMath1351.05123arXiv1310.1376OpenAlexW1570138350MaRDI QIDQ729758
Carl Georg Heise, Ping Yang, Julia Ehrenmüller, Amy N. Yates, Songling Shan, Guantao Chen, Cristina G. Fernandes
Publication date: 22 December 2016
Published in: Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1310.1376
Paths and cycles (05C38) Planar graphs; geometric and topological aspects of graph theory (05C10) Distance in graphs (05C12)
Related Items (19)
Well-partitioned chordal graphs ⋮ Nonempty intersection of longest paths in \(2K_2\)-free graphs ⋮ Improvements on Hippchen's conjecture ⋮ Order of the smallest counterexample to Gallai's conjecture ⋮ Nonempty intersection of longest paths in a graph with a small matching number ⋮ All longest cycles in a 2‐connected partial 3‐tree share a common vertex ⋮ Bonds Intersecting Long Paths in \(k\) -Connected 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 ⋮ Nonempty intersection of longest paths in graphs without forbidden pairs ⋮ Intersection of longest paths in graph classes ⋮ Gallai's question and constructions of almost hypotraceable graphs ⋮ Unnamed Item ⋮ Reducing graph transversals via edge contractions ⋮ Transversals of longest paths ⋮ Using edge contractions to reduce the semitotal domination number ⋮ \(\alpha\)-diperfect digraphs
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Intersecting longest paths
- Linear time algorithms for NP-hard problems restricted to partial k- trees
- Planar and infinite hypohamiltonian and hypotraceable graphs
- Über längste Wege und Kreise in Graphen
- Counting \(H-\)colorings of partial \(k-\)trees
- HAMILTONian circuits in chordal bipartite graphs
- The longest path problem is polynomial on cocomparability graphs
- Vertices missed by longest paths or circuits
- Smallest Sets of Longest Paths with Empty Intersection
- WHEN DO THREE LONGEST PATHS HAVE A COMMON VERTEX?
- On Linear Time Minor Tests with Depth-First Search
- On longest paths and circuits in graphs.
- Graph Classes: A Survey
- Longest Paths in Circular Arc Graphs
- Intersecting longest paths and longest cycles: A survey
- Über die Nichtexistenz eines Knotenpunktes, durch den alle längsten Wege eines Graphen gehen
- A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
- Research problems
This page was built for publication: Nonempty intersection of longest paths in series-parallel graphs