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 › Scientific › peer-review

2 Citations (SciVal)

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 3ⁿ+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	https://doi.org/10.1137/21M1406155
Publication status	Published - 2021
Externally published	Yes

Keywords

Isometric embedding
Labelling scheme
Universal graph

Access to Document

10.1137/21M1406155

Cite this

@article{a2fa691c07904f0d994a7b4198621f00,

title = "Isometric universal graphs",

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

keywords = "Isometric embedding, Labelling scheme, Universal graph",

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

year = "2021",

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

number = "2",

}

TY - JOUR

T1 - Isometric universal graphs

AU - Esperet, Louis

AU - Gavoille, Cyril

AU - Groenland, Carla

PY - 2021

Y1 - 2021

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

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

KW - Isometric embedding

KW - Labelling scheme

KW - Universal graph

UR - http://www.scopus.com/inward/record.url?scp=85108718743&partnerID=8YFLogxK

U2 - 10.1137/21M1406155

DO - 10.1137/21M1406155

M3 - Article

AN - SCOPUS:85108718743

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

Other files and links

Fingerprint

Cite this