Graph embeddings into Hamming spaces

MaRDI QIDQ6312320zbMATH OpenFDO

Authors Dominic van der Zypen

Publication date 10 January 2019

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Nonnumerical algorithms (68W05)

Abstract: Graph embeddings deal with injective maps from a given simple, undirected graph $G=(V,E)$ into a metric space, such as $mathbb{R}^n$ with the Euclidean metric. This concept is widely studied in computer science, see cite{ge1}, but also offers attractive research in pure graph theory cite{ge2}. In this note we show that any graph can be embedded into a particularly simple metric space: ${0,1}^n$ with the Hamming distance, for large enough $n$.

This page was built for publication: Graph embeddings into Hamming spaces

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