Levenshtein Graphs: Resolvability, Automorphisms & Determining Sets

DOI10.1016/J.DISC.2022.113310MaRDI QIDQ6372843arXivFDO

Authors Perrin E. Ruth, Manuel E. Lladser

Publication date 14 July 2021

Published in arXiv

Full work available at URL https://doi.org/10.1016/J.DISC.2022.113310

Mathematics Subject Classification ID

Distance in graphs (05C12) Combinatorial codes (94B25)

arXiv classification

cs.DMcs.DSmath.CO

Abstract: We introduce the notion of Levenshtein graphs, an analog to Hamming graphs but using the edit distance instead of the Hamming distance; in particular, Levenshtein graphs allow for underlying strings (nodes) of different lengths. We characterize various properties of these graphs, including a necessary and sufficient condition for their geodesic distance to be identical to the edit distance, their automorphism group and determining number, and an upper bound on their metric dimension. Regarding the latter, we construct a resolving set composed of two-run strings and an algorithm that computes the edit distance between a string of length $k$ and any single-run or two-run string in $O(k)$ operations.

This page was built for publication: Levenshtein Graphs: Resolvability, Automorphisms & Determining Sets

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