Bi-Lipschitz embedding properties of lamplighter graphs on weighted and unweighted trees

Read full text
Authors: Charlotte Melby, Beata Randrianantoanina
Cited by: 0

Abstract

In 2021, F. Baudier, P. Motakis, Th. Schlumprecht and A. Zsák proved that if a sequence $(G_k)_{k\in{\mathbb{N}}}$ of graphs contains the sequence of complete graphs with uniformly bounded distortion, then the sequence of lamplighter graphs on $G_k$'s contains Hamming cubes with uniformly bounded distortion and asked whether the converse holds. They suggested that a sequence of trees with edges replaced by paths of "moderately growing" lengths may be a counterexample. We prove that indeed this is the case, and that a sequence of "moderately" weighted trees is another counterexample. Further, we prove that diamond graphs do not embed with uniformly bounded distortion into lamplighter graphs on trees with edges replaced by paths with sufficiently fast growing lengths.

Fields of Study & Subjects

Graph theory and applications Complex Network Analysis Techniques Advanced Graph Theory Research

Publication details

Journal / source
Carpathian Mathematical Publications
Volume
18
Issue
1
Pages
222–235
Publication date
13 June 2026
Language
EN