Shifting paths to avoidable ones

DOI10.1002/jgt.22766zbMath1522.05238arXiv2008.01128OpenAlexW3212579703MaRDI QIDQ6057583

Vladimir A. Gurvich, Mikhail N. Vyalyi, Matjaž Krnc, Martin Milanič

Publication date: 5 October 2023

Published in: Journal of Graph Theory (Search for Journal in Brave)

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

zbMATH Keywords

cyclepathisometric pathwalkreconfigurationclosed walkshiftinginduced pathtrailavoidable walk

Mathematics Subject Classification ID

Trees (05C05) Paths and cycles (05C38) Distance in graphs (05C12) Graph operations (line graphs, products, etc.) (05C76)

Related Items

Computing and listing avoidable vertices and paths ⋮ Computing and listing avoidable vertices and paths ⋮ Avoidable vertices and edges in graphs: existence, characterization, and applications

Cites Work

• Unnamed Item
• Unnamed Item
• The complexity of rerouting shortest paths
• Minimal triangulation of a graph and optimal pivoting order in a sparse matrix
• Separability generalizes Dirac's theorem
• Dirac-type characterizations of graphs without long chordless cycles
• Avoidable paths in graphs
• Avoidable vertices and edges in graphs
• Reconfiguring undirected paths
• Vertex elimination orderings for hereditary graph classes
• Algorithmic Aspects of Vertex Elimination on Graphs