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 -
On the number of regular edge labelings

Authors: Kevin Buchin ORCID-iD1; Bettina Speckmann ORCID-iD1; Sander Verdonschot 2

  • 1 Department of mathematics and computing science [Eindhoven]
  • 2 School of Computer Science (Carleton, Ottawa)

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).

Volume: Vol. 16 no. 3
Section: Combinatorics
Published on: October 20, 2014
Submitted on: December 27, 2011
Keywords: regular edge labeling,counting,Shearer’s entropy lemma,[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]
    Source : OpenAIRE Graph
  • Funder: Natural Sciences and Engineering Research Council of Canada
  • Algorithmic Foundations for the Analysis and Visualization of Complex Moving Objects; Funder: Netherlands Organisation for Scientific Research (NWO); Code: 639.023.208
  • A framework for progressive, user-steered algorithms in visual analytics; Funder: Netherlands Organisation for Scientific Research (NWO); Code: 612.001.207

Linked publications - datasets - softwares

Source : ScholeXplorer IsRelatedTo DOI 10.1007/978-3-642-15775-2_10
  • 10.1007/978-3-642-15775-2_10
  • 10.1007/978-3-642-15775-2_10
On the number of spanning trees a planar graph can have

Consultation statistics

This page has been seen 265 times.
This article's PDF has been downloaded 398 times.