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


Reconfiguration graphs of shortest paths
Authors:John Asplund  Kossi Edoh  Ruth Haas  Yulia Hristova  Beth Novick  Brett Werner
Institution:1. Department Of Technology and Mathematics, Dalton State College, Dalton, GA 30720, USA;2. Department of Mathematics, North Carolina Agricultural and Technical State University, Greensboro, NC 27411, USA;3. Department of Mathematics, University of Hawaii at Manoa, Honolulu, HI 96822, USA;4. Smith College, Northampton, MA 01063, United States;5. Department of Mathematics and Statistics, University of Michigan - Dearborn, Dearborn, MI 48128, USA;6. Department of Mathematical Sciences, Clemson University, Clemson, SC 29634, USA;7. Department of Mathematics, University of Colorado, Boulder Boulder, CO 80309, USA
Abstract:For a graph G anda,bV(G), the shortest path reconfiguration graph of G with respect to a andb is denoted by S(G,a,b). The vertex set of S(G,a,b) is the set of all shortest paths between a andb in G. Two vertices in V(S(G,a,b)) are adjacent, if their corresponding paths in G differ by exactly one vertex. This paper examines the properties of shortest path graphs. Results include establishing classes of graphs that appear as shortest path graphs, decompositions and sums involving shortest path graphs, and the complete classification of shortest path graphs with girth 5 or greater. We include an infinite family of well structured examples, showing that the shortest path graph of a grid graph is an induced subgraph of a lattice.
Keywords:Reconfiguration graphs  Shortest paths  Girth  Grid graph
本文献已被 ScienceDirect 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

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