Discrete Mathematics & Theoretical Computer Science, Vol 16, No 3 (2014)

Font Size:  Small  Medium  Large

On the Number of Regular Edge Labelings

Kevin Buchin, Bettina Speckmann, Sander Verdonschot

Abstract


We prove that any irreducible triangulation on n vertices has O(4.6807n) regular edge labelings and that there are irreducible triangulations on n vertices with Ω(3.0426n) regular edge labelings. Our upper bound relies on a novel application of Shearer's entropy lemma. As an example of the wider applicability of this technique, we also improve the upper bound on the number of 2-orientations of a quadrangulation to O(1.87n).

Full Text: PDF