Isometric universal graphs

Louis Esperet, Cyril Gavoille, Carla Groenland

Research output: Contribution to journalArticleScientificpeer-review

1 Citation (Scopus)

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 languageEnglish
Pages (from-to)1224-1237
Number of pages14
JournalSIAM Journal on Discrete Mathematics
Volume35
Issue number2
DOIs
Publication statusPublished - 2021
Externally publishedYes

Keywords

  • Isometric embedding
  • Labelling scheme
  • Universal graph

Fingerprint

Dive into the research topics of 'Isometric universal graphs'. Together they form a unique fingerprint.

Cite this