Skip to Main content Skip to Navigation
Journal articles

On the number of regular edge labelings

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).
Document type :
Journal articles
Complete list of metadata

Cited literature [29 references]  Display  Hide  Download

https://hal.inria.fr/hal-01188899
Contributor : Coordination Episciences Iam Connect in order to contact the contributor
Submitted on : Monday, August 31, 2015 - 5:03:04 PM
Last modification on : Thursday, September 7, 2017 - 1:03:42 AM
Long-term archiving on: : Tuesday, December 1, 2015 - 10:41:27 AM

File

dmtcs-16-3-12.pdf
Publisher files allowed on an open archive

Identifiers

Collections

Citation

Kevin Buchin, Bettina Speckmann, Sander Verdonschot. On the number of regular edge labelings. Discrete Mathematics and Theoretical Computer Science, DMTCS, 2014, Vol. 16 no. 3 (3), pp.215--228. ⟨10.46298/dmtcs.2085⟩. ⟨hal-01188899⟩

Share

Metrics

Record views

45

Files downloads

700