Bounding the distance among longest paths in a connected graph |
| |
Authors: | Jan Ekstein Shinya Fujita Adam Kabela Jakub Teska |
| |
Affiliation: | 1. Department of Mathematics, Institute for Theoretical Computer Science, and European Centre of Excellence NTIS - New Technologies for the Information Society, Faculty of Applied Sciences, University of West Bohemia, Pilsen, Technická 8, 306 14 Plzeň, Czech Republic;2. International College of Arts and Sciences, Yokohama City University, 22-2 Seto, Kanazawa-ku, Yokohama 236-0027, Japan |
| |
Abstract: | It is easy to see that in a connected graph any longest paths have a vertex in common. For , Skupień in 1966 obtained a connected graph in which some longest paths have no common vertex, but every longest paths have a common vertex. It is not known whether every longest paths in a connected graph have a common vertex and similarly for 4, 5, and longest path. Fujita et al. in 2015 give an upper bound on distance among longest paths in a connected graph. In this paper we give a similar upper bound on distance between longest paths and also for longest paths, in general. |
| |
Keywords: | Longest paths Path intersection |
本文献已被 ScienceDirect 等数据库收录! |
|