Abstract
A subgraph 𝐻
of a graph 𝐺
is isometric if the distances between vertices in 𝐻
coincide with the distances between the corresponding vertices in 𝐺
. We show that for any integer 𝑛≥1
, there is a graph on 3𝑛+𝑂(log2𝑛)
vertices that contains isometric copies of all 𝑛
-vertex graphs. Our main tool is a new type of distance labelling scheme, whose study might be of independent interest.
of a graph 𝐺
is isometric if the distances between vertices in 𝐻
coincide with the distances between the corresponding vertices in 𝐺
. We show that for any integer 𝑛≥1
, there is a graph on 3𝑛+𝑂(log2𝑛)
vertices that contains isometric copies of all 𝑛
-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 - Jan 2021 |
Keywords
- labelling scheme
- isometric embedding
- universal graph