Isometric Universal Graphs

Louis Esperet; Cyril Gavoille; Carla Groenland

doi:10.1137/21m1406155

Isometric Universal Graphs

Louis Esperet
, Cyril Gavoille
, Carla Groenland

Research output: Contribution to journal › Article › Academic › peer-review

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.

Original language	English
Pages (from-to)	1224-1237
Number of pages	14
Journal	SIAM Journal on Discrete Mathematics
Volume	35
Issue number	2
DOIs	https://doi.org/10.1137/21m1406155
Publication status	Published - Jan 2021

Keywords

labelling scheme
isometric embedding
universal graph

Access to Document

10.1137/21m1406155

21m1406155Final published version, 363 KBLicence: Taverne

Cite this

@article{68be591eaaa64f118af449f1491d4261,

title = "Isometric Universal Graphs",

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.",

keywords = "labelling scheme, isometric embedding, universal graph",

author = "Louis Esperet and Cyril Gavoille and Carla Groenland",

year = "2021",

month = jan,

doi = "10.1137/21m1406155",

language = "English",

volume = "35",

pages = "1224--1237",

journal = "SIAM Journal on Discrete Mathematics",

issn = "0895-4801",

publisher = "Society for Industrial and Applied Mathematics Publications",

number = "2",

}

TY - JOUR

T1 - Isometric Universal Graphs

AU - Esperet, Louis

AU - Gavoille, Cyril

AU - Groenland, Carla

PY - 2021/1

Y1 - 2021/1

N2 - 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.

AB - 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.

KW - labelling scheme

KW - isometric embedding

KW - universal graph

U2 - 10.1137/21m1406155

DO - 10.1137/21m1406155

M3 - Article

SN - 0895-4801

VL - 35

SP - 1224

EP - 1237

JO - SIAM Journal on Discrete Mathematics

JF - SIAM Journal on Discrete Mathematics

IS - 2

ER -

Isometric Universal Graphs

Abstract

Keywords

Access to Document

Fingerprint

Cite this