Nonempty intersection of longest paths in series-parallel graphs

DOI10.1016/j.disc.2016.07.023zbMath1351.05123arXiv1310.1376MaRDI 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

zbMATH Keywords

outerplanar graphs; Gallai's question

Mathematics Subject Classification ID

05C38: Paths and cycles

05C10: Planar graphs; geometric and topological aspects of graph theory

05C12: Distance in graphs

Related Items

Order of the smallest counterexample to Gallai's conjecture, Unnamed Item, Intersection of longest paths in graph classes, Transversals of longest paths, All longest cycles in a 2‐connected partial 3‐tree share a common vertex, Bonds Intersecting Long Paths in \(k\) -Connected Graphs, 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

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