Les hypercartes planaires sont des arbres tres bien etiquetes

✍ Scribed by Didier Arques

• Book ID: 103056706
• Publisher: Elsevier Science
• Year: 1986
• Tongue: English
• Weight: 801 KB
• Volume: 58
• Category: Article
• ISSN: 0012-365X
• DOI: 10.1016/0012-365x(86)90182-2

✦ Synopsis

R. Coil and B. Vauquelin have constructed (cf [1]) a one to one correspondence from rooted planar maps onto rooted well-labeled trees (trees whose vertices are labeled with natural numbers that differ by at most one on adjacent vertices). This correspondence does not associate other families of planar maps (e.g. planar hypermaps,...) and easily definable families of trees. The main result of this paper (Theorem 1, Section 1I) is to construct a new one to one correspondence from rooted planar maps onto rooted well-labeled trees which also associates rooted planar hypermaps with n edge-ends (called 'brin' in French) and rooted very well-labeled trees (well labeled trees whose adjacent vertices have not the same label) with n edges. This last result is given in Section 3, Theorem 2.

The coding of rooted very well-labeled trees by words extending Dyck's words (or parenthesis systems), allows their enumeration, hence the enumeration of rooted planar hypermaps. This side is the subject of a work in progress under B. Vauquelin.