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