×

zbMATH — the first resource for mathematics

Counting unrooted maps on the plane. (English) Zbl 1112.05054
A plane map is a 2-cell imbedding of a connected multigraph (loops and multiple edges allowed) on the sphere, with a distinguished face. The map is rooted by also distinguishing an oriented edge; an unrooted plane map is an equivalence class of plane maps under orientation-preserving homeomorphism. In a series of three papers [Can. J. Math. 35, 417–435 (1983; Zbl 0519.05041); Discrete Math. 282, No. 1–3, 209–221 (2004; Zbl 1051.05049) and Eur. J. Comb. 26, No. 5, 651–663 (2005; Zbl 1070.05050)], the authors enumerated unrooted planar (no distinguished face) \(n\)-edge maps of various classes, including all maps, non-separable maps, Eulerian maps, and loopless maps. In the present paper, they employ the same technique to get closed formulae for counting unrooted plane maps of all these classes and their duals. In contrast to the rooted case, where the corresponding formulae are all sum-free, the formulae obtained for unrooted maps contain a sum over the divisors of \(n\). Also counted are unrooted two-vertex plane maps.

MSC:
05C30 Enumeration in graph theory
Software:
OEIS
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Bousquet, M.; Labelle, G.; Leroux, P., Enumeration of planar two-face maps, Discrete math., 222, 1-25, (2000) · Zbl 0993.05089
[2] Brown, W.G., Enumeration of non-separable planar maps, Canad. J. math., 15, 3, 526-545, (1963) · Zbl 0115.40901
[3] Harary, F.; Prins, G.; Tutte, W.T., The number of plane trees, Indag. math., 26, 319-329, (1964) · Zbl 0126.19002
[4] Koganov, L.M.; Liskovets, V.A.; Walsh, T.R.S., Total vertex enumeration in rooted planar maps, Ars combin., 54, 149-160, (2000) · Zbl 0993.05087
[5] Labelle, G., Une nouvelle démonstration combinatoire des formules d’inversion de Lagrange, Adv. math., 42, 3, 217-247, (1981) · Zbl 0477.05007
[6] Liskovets, V.A., A census of non-isomorphic planar maps, (), 479-494 · Zbl 0519.05040
[7] Liskovets, V.A., Counting unrooted maps on the oriented plane, Graph theory newslett., 11, 5, 3, (1982)
[8] Liskovets, V.A., Enumeration of non-isomorphic planar maps, Selecta math. soviet., 4, 4, 303-323, (1985) · Zbl 0578.05033
[9] Liskovets, V.A., Enumerative formulae for unrooted planar maps: a pattern, Electron. J. combin., 11, 1, R88, (2004) · Zbl 1060.05046
[10] Liskovets, V.A.; Walsh, T.R.S., The enumeration of non-isomorphic 2-connected planar maps, Canad. J. math., 35, 3, 417-435, (1983) · Zbl 0519.05041
[11] Liskovets, V.A.; Walsh, T.R.S., Enumeration of Eulerian and unicursal planar maps, Discrete math., 282, 209-221, (2004) · Zbl 1051.05049
[12] Liskovets, V.A.; Walsh, T.R.S., Counting unrooted loopless planar maps, European J. combin., 26, 5, 651-663, (2005) · Zbl 1070.05050
[13] Petkovšek, M.; Wilf, H.S.; Zeilberger, D., \(a = b\), (1996), A.K. Peters Wellesley, MA, 212 pp
[14] (), 1232 pp
[15] Sloane, N.J.A., The on-line encyclopedia of integer sequences, (2005), Published electronically at · Zbl 1274.11001
[16] Tutte, W.T., A census of planar maps, Canad. J. math., 15, 2, 249-271, (1963) · Zbl 0115.17305
[17] Walkup, D.W., The number of plane trees, Mathematika, 19, 2, 200-204, (1972) · Zbl 0253.05106
[18] Walsh, T.R.S., Hypermaps versus bipartite maps, J. combin. theory ser. B, 18, 2, 155-163, (1975) · Zbl 0302.05101
[19] Walsh, T.R.S., Efficient enumeration of sensed planar maps, Discrete math., 293, 263-289, (2005) · Zbl 1063.05070
[20] Walsh, T.R.S.; Lehman, A.B., Counting rooted maps by genus. III: non-separable maps, J. combin. theory ser. B, 18, 3, 222-259, (1975) · Zbl 0299.05110
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.