2021/08/31 by Matjaž Krnc, Krnc, Matjaž, Nevena Pivač +1
Computer Science · #Advanced Graph Theory Research #Combinatorics (math.CO) #Constraint Satisfaction and Optimization #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Graph Theory and Algorithms
paper · pdf · doi:10.48550/arxiv.2109.00035
openalex publication_date 2021/08/31 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Graph searching is one of the simplest and most widely used tools in graph algorithms. Every graph search method is defined using some particular selection rule, and the analysis of the corresponding vertex orderings can aid greatly in devising algorithms, writing proofs of correctness, or recognition of various graph families. We study graphs where the sets of vertex orderings produced by two different search methods coincide. We characterise such graph families for ten pairs from the best-known set of graph searches: Breadth First Search (BFS), Depth First Search (DFS), Lexicographic Breadth First Search (LexBFS) and Lexicographic Depth First Search (LexDFS), and Maximal Neighborhood Search (MNS).