Classification of reconfiguration graphs of shortest path graphs with no induced 4-cycles

DOI10.1016/J.DISC.2019.111640MaRDI QIDQ2279287zbMATH OpenOpenAlexFDO

Authors John Asplund, Brett M. Werner

Publication date 12 December 2019

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1808.09387

zbMATH Keywords

reconfiguration graphshortest path graph

Mathematics Subject Classification ID

Distance in graphs (05C12) Extremal problems in graph theory (05C35) Paths and cycles (05C38)

Abstract: For any graph $G$ with $a,binV(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., extit{Reconfiguration graphs of shortest paths}, Discrete Mathematics extbf{341} (2018), no. 10, 2938--2948], 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.

Recommendations

• Reconfiguration graphs of shortest paths
• A reconstrability conjecture for graphs with restrictions for 4-vertex simple paths
• Reconfiguration of vertex-disjoint shortest paths on graphs
• On 4-connected graphs without even cycle decompositions
• Nonseparating Cycles in 4-Connected Graphs
• Acyclic 4-choosability of planar graphs without adjacent short cycles
• On relating edges in graphs without cycles of length 4
• Acyclic 4-choosability of planar graphs without intersecting short cycles
• Decompositions of some classes of regular graphs and digraphs into cycles of length 4p
• Efficiently recognizing the P₄-structure of trees and of bipartite graphs without short cycles

Cites work

• Connectedness of the graph of vertex-colourings
• Finding paths between 3-colorings
• Finding paths between graph colourings: PSPACE-completeness and superpolynomial distances
• Mixing 3-colourings in bipartite graphs
• Motion planning with pulley, rope, and baskets
• On the complexity of reconfiguration problems
• PSPACE-completeness of sliding-block puzzles and other problems through the nondeterministic constraint logic model of computation
• Reconfiguration graphs for vertex colourings of chordal and chordal bipartite graphs
• Reconfiguration graphs of shortest paths
• Reconfiguration of list edge-colorings in a graph
• Shortest paths between shortest paths
• The complexity of rerouting shortest paths

Cited in

(4)

• Reconfiguration graphs of shortest paths
• Shifting paths to avoidable ones
• Reconfiguring shortest paths in graphs
• Rerouting planar curves and disjoint paths

This page was built for publication: Classification of reconfiguration graphs of shortest path graphs with no induced 4-cycles

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2279287)