On the number of regular edge labelings

K. Buchin, B. Speckmann, S. Verdonschot

Onderzoeksoutput: Bijdrage aan tijdschriftTijdschriftartikelAcademicpeer review

55 Downloads (Pure)

Samenvatting

We prove that any irreducible triangulation on n vertices has O (4:6807n ) regular edge labeling,s 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 ). Keywords: Counting; Regular edge labeling; Shearer's entropy lemma
Originele taal-2Engels
Pagina's (van-tot)215-228
TijdschriftDiscrete Mathematics and Theoretical Computer Science
Volume16
Nummer van het tijdschrift3
StatusGepubliceerd - 2014

Vingerafdruk Duik in de onderzoeksthema's van 'On the number of regular edge labelings'. Samen vormen ze een unieke vingerafdruk.

Citeer dit