 |
Discrete Mathematics & Theoretical Computer Science |
Kevin Buchin ; Bettina Speckmann ; Sander Verdonschot - On the number of regular edge labelings
dmtcs:2085 - Discrete Mathematics & Theoretical Computer Science, October 20, 2014, Vol. 16 no. 3 - https://doi.org/10.46298/dmtcs.2085On the number of regular edge labelingsArticle
Authors: Kevin Buchin 
1,2; Bettina Speckmann 1,2; Sander Verdonschot 3
- 1 Department of mathematics and computing science [Eindhoven]
- 2 Department of Mathematics and Computer Science [Eindhoven]
- 3 School of Computer Science (Carleton, Ottawa)
Combinatorics
[en]
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).
Source: HAL:hal-01188899v1
Volume: Vol. 16 no. 3
Section: Combinatorics
Published on: October 20, 2014
Imported on: December 27, 2011
Keywords: [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], [en] regular edge labeling, counting, Shearer’s entropy lemma
Funding:
- Source : OpenAIRE Graph
- Funder: Natural Sciences and Engineering Research Council of Canada
- Algorithmic Foundations for the Analysis and Visualization of Complex Moving Objects; Funder: Natural Sciences and Engineering Research Council of Canada; Code: 639.023.208
- A framework for progressive, user-steered algorithms in visual analytics; Funder: Natural Sciences and Engineering Research Council of Canada; Code: 612.001.207
Consultation statistics
This page has been seen 604 times.
This article's PDF has been downloaded 1028 times.