A Note on Diameter Certification in Trees

Abstract

In the local certification model, certifying the diameter of general graphs requires large certificates, but trees admit more efficient solutions. In this note, we provide a $1$-local certification scheme that certifies whether the diameter of a given tree is at most $d$ using certificates of at most $3\lceil\log_2(d+1)\rceil$ bits.