Isometric universal graphs

DOI10.1137/21M1406155MaRDI QIDQ4992841zbMATH OpenFDO

Authors L. Esperet, Cyril Gavoille, Carla Groenland

Publication date 10 June 2021

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2103.08570

zbMATH Keywords

isometric embeddinglabelling schemeuniversal graph

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Distance in graphs (05C12) Graph labelling (graceful graphs, bandwidth, etc.) (05C78)

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 $nge1$, there is a graph on $3^{n+O(lo{g}^{2}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.

Recommendations

• Isometric embeddings of graphs
• On a conjecture about the existence of isometric subgraphs
• Isometric subgraphs for Steiner distance
• Isometric subgraphs of Hamming graphs and d-convexity
• scientific article; zbMATH DE number 4066951

Cites work

• A data structure for dynamic trees
• A Separator Theorem for Nonplanar Graphs
• A Separator Theorem for Planar Graphs
• Adjacency labeling schemes and induced-universal graphs
• Asymptotically optimal induced universal graphs
• Better distance labeling for unweighted planar graphs
• Distance labeling in graphs
• Distance labeling schemes for trees
• Graphs which contain all small graphs
• Hardness of exact distance queries in sparse graphs through hub labeling
• scientific article; zbMATH DE number 3747149 (Why is no real title available?)
• scientific article; zbMATH DE number 16297 (Why is no real title available?)
• scientific article; zbMATH DE number 3395950 (Why is no real title available?)
• Implicat Representation of Graphs
• Labeling Schemes for Small Distances in Trees
• On minimal n-universal graphs
• Optimal distance labeling schemes for trees
• Proof of the squashed cube conjecture
• Shorter Implicit Representation for Planar Graphs and Bounded Treewidth Graphs
• Shorter Labeling Schemes for Planar Graphs
• Simpler, faster and shorter labels for distances in graphs
• Sublinear Distance Labeling
• Sublinear-space distance labeling using hubs

Cited in

(6)

• Universal geometric graphs
• Isometric subgraphs for Steiner distance
• On a conjecture about the existence of isometric subgraphs
• Induced subgraphs of zero-divisor graphs
• Super graphs on groups. II
• Title not available (Why is no real title available?)

This page was built for publication: Isometric universal graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4992841)