Total vertex enumeration in rooted planar maps. (English) Zbl 0993.05087

Koganov, Leonid M.; Liskovets, Valery A.; Walsh, Timothy R. S.

Ars Comb. 54, 149-160 (2000).

The authors prove that the total number of vertices in all rooted planar Eulerian maps with \(n\) edges is \((n+2)/3\) times the number of such maps. They prove also an analogous relation, with the coefficient \((5n^2+13n+2)/(8n+2)\), for rooted planar loopless maps. (Simple formulas for numbers of these maps are well known.) Two different proofs for both classes of maps are given, one by Lagrange inversion and the other binomial. To find a direct proof of these combinatorial identities is posed as a problem.

Reviewer: Martin Klazar (Praha)

MSC:

05C30	Enumeration in graph theory
05C10	Planar graphs; geometric and topological aspects of graph theory
05A19	Combinatorial identities, bijective combinatorics

Keywords:

enumeration; rooted planar map; Eulerian map; loopless map