Bounding the distance among longest paths in a connected graph

DOI10.1016/J.DISC.2017.09.029zbMATH Open1380.05109arXiv1607.08850OpenAlexW2964030017MaRDI QIDQ1699570FDOQ1699570

Jakub Teska, Jan Ekstein, Shinya Fujita, Adam Kabela

Publication date: 23 February 2018

Published in: Discrete Mathematics (Search for Journal in Brave)

Abstract: It is easy to see that in a connected graph any 2 longest paths have a vertex in common. For k>=7, Skupien in [7] obtained a connected graph in which some k longest paths have no common vertex, but every k-1 longest paths have a common vertex. It is not known whether every 3 longest paths in a connected graph have a common vertex and similarly for 4, 5, and 6 longest path. In [5] the authors give an upper bound on distance among 3 longest paths in a connected graph. In this paper we give a similar upper bound on distance between 4 longest paths and also for k longest paths, in general.

Full work available at URL: https://arxiv.org/abs/1607.08850

zbMATH Keywords

longest pathspath intersection

Mathematics Subject Classification ID

Distance in graphs (05C12) Paths and cycles (05C38) Connectivity (05C40)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Smallest sets of longest paths with empty intersection
• WHEN DO THREE LONGEST PATHS HAVE A COMMON VERTEX?
• Intersecting longest paths
• Longest Paths in Circular Arc Graphs
• Über die Nichtexistenz eines Knotenpunktes, durch den alle längsten Wege eines Graphen gehen
• Planar and infinite hypohamiltonian and hypotraceable graphs
• On longest paths and circuits in graphs.
• A new approach towards a conjecture on intersecting three longest paths

Cited In (2)

• On approximating the longest path in a graph
• Title not available (Why is that?)

Recommendations

• Title not available (Why is that?) 👍 👎
• Title not available (Why is that?) 👍 👎
• Title not available (Why is that?) 👍 👎
• On approximating the longest path in a graph 👍 👎
• On approximating the longest path in a graph 👍 👎
• Long cycles and paths in distance graphs 👍 👎
• Relative length of longest paths and cycles in graphs 👍 👎
• On the distance connectivity of graphs and digraphs 👍 👎
• Longest paths joining given vertices in a graph 👍 👎
• Relative Length of Longest Paths and Cycles in 2-Connected Graphs 👍 👎

This page was built for publication: Bounding the distance among longest paths in a connected graph

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