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


On the diameter of geometric path graphs of points in convex position
Authors:Jou-Ming Chang  Ro-Yu Wu
Affiliation:a Department of Information Management, National Taipei College of Business, Taipei, Taiwan, ROC
b Department of Industrial Engineering Management, Lunghwa University of Science and Technology, Taoyuan, Taiwan, ROC
Abstract:For a set S of n points in convex position in the plane, let P(S) denote the set of all plane spanning paths of S. The geometric path graph of S, denoted by Gn, is the graph with P(S) as its vertex set and two vertices P,QP(S) are adjacent if and only if P and Q can be transformed to each other by means of a single edge replacement. Recently, Akl et al. S.G. Akl, K. Islam, H. Meijer, On planar path transformation, Inform. Process. Lett. 104 (2007) 59-64] showed that the diameter of Gn is at most 2n−5. In this note, we derive the exact diameter of Gn for n?3.
Keywords:Combinatorial problems  Flip  Plane spanning path  Geometric path graph  Diameter
本文献已被 ScienceDirect 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

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