首页 | 本学科首页   官方微博 | 高级检索  
     检索      


Bounding the distance among longest paths in a connected graph
Authors:Jan Ekstein  Shinya Fujita  Adam Kabela  Jakub Teska
Institution: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 2 longest paths have a vertex in common. For k7, Skupień in 1966 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. Fujita et al. in 2015 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.
Keywords:Longest paths  Path intersection
本文献已被 ScienceDirect 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号