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


Classification of reconfiguration graphs of shortest path graphs with no induced 4-cycles
Abstract:For any graph G with a,bV(G), a shortest path reconfiguration graph can be formed with respect to a and b; we denote such a graph as S(G,a,b). The vertex set of S(G,a,b) is the set of all shortest paths from a to b in G while two vertices U,W in V(S(G,a,b)) are adjacent if and only if the vertex sets of the paths that represent U and W differ in exactly one vertex. In a recent paper (Asplund et al., 2018), it was shown that shortest path graphs with girth five or greater are exactly disjoint unions of even cycles and paths. In this paper, we extend this result by classifying all shortest path graphs with no induced 4-cycles.
Keywords:Shortest path graph  Reconfiguration graph
本文献已被 ScienceDirect 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

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