Abstract
A subgraph H of a graph G is isometric if the distances between vertices in H coincide with the distances between the corresponding vertices in G. We show that for any integer ngeqslant 1, there is a graph on 3n+O(log2 n) vertices that contains isometric copies of all n-vertex graphs. Our main tool is a new type of distance labelling scheme, whose study might be of independent interest.
Original language | English |
---|---|
Pages (from-to) | 1224-1237 |
Number of pages | 14 |
Journal | SIAM Journal on Discrete Mathematics |
Volume | 35 |
Issue number | 2 |
DOIs | |
Publication status | Published - 2021 |
Externally published | Yes |
Keywords
- Isometric embedding
- Labelling scheme
- Universal graph