zbMATH — the first resource for mathematics

4-edge-connected 4-regular maps on the projective plane. (English) Zbl 1444.05047
Summary: In this paper rooted (near-)4-regular maps on the projective plane are investigated with respect to the root-valency, the number of edges, the number of inner faces, the number of nonroot-vertex-loops and the number of separating cycles. In particular, 4-edge connected 4-regular maps (which are related to the 3-flow conjecture by Tutte) are handled. Formulae of several types of rooted 4-edge-connected 4-regular maps on the projective plane are presented. Several known results on the number of 4-regular maps on the projective plane are also derived. Finally, using Darboux’s method, a nice asymptotic formula for the numbers of this type of maps is given which implies that almost every (loopless) 4-regular map on the projective plane has a separating cycle.
05C10 Planar graphs; geometric and topological aspects of graph theory
05C30 Enumeration in graph theory
05C45 Eulerian and Hamiltonian graphs
Full Text: DOI
[1] D. Arqu‘es, Relations fonctionnelles et d´enombrement des cartes point´ees sur le tore,J. Comb. Theory Ser. B43(1987), 253-274, doi:10.1016/0095-8956(87)90002-5.
[2] E. A. Bender, Asymptotic methods in enumeration,SIAM Rev.16(1974), 485-515, doi:10. 1137/1016082. · Zbl 0294.05002
[3] E. A. Bender and E. R. Canfield, The number of rooted maps on an orientable surface,J. Comb. Theory Ser. B53(1991), 293-299, doi:10.1016/0095-8956(91)90079-y. · Zbl 0751.05052
[4] E. A. Bender, E. R. Canfield and L. B. Richmond, The asymptotic number of rooted maps on a surface. II. Enumeration by vertices and faces,J. Comb. Theory Ser. A63(1993), 318-329, doi:10.1016/0097-3165(93)90063-e. · Zbl 0777.05065
[5] E. A. Bender, E. R. Canfield and R. W. Robinson, The enumeration of maps on the torus and the projective plane,Canad. Math. Bull.31(1988), 257-271, doi:10.4153/cmb-1988-039-4. · Zbl 0617.05036
[6] E. A. Bender, Z. Gao and L. B. Richmond, Almost all rooted maps have large representativity, J. Graph Theory18(1994), 545-555, doi:10.1002/jgt.3190180603. · Zbl 0809.05060
[7] E. A. Bender and L. B. Richmond, A survey of the asymptotic behaviour of maps,J. Comb. Theory Ser. B40(1986), 297-329, doi:10.1016/0095-8956(86)90086-9.
[8] J. A. Bondy and U. S. R. Murty,Graph Theory with Applications, Elsevier, New York, 1976. · Zbl 1226.05083
[9] W. G. Brown, Enumeration of non-separable planar maps,Canadian J. Math.15(1963), 526- 545, doi:10.4153/cjm-1963-056-7. · Zbl 0115.40901
[10] W. G. Brown, Enumeration of quadrangular dissections of the disk,Canadian J. Math.17 (1965), 302-317, doi:10.4153/cjm-1965-030-1. · Zbl 0138.19104
[11] W. G. Brown, On the existence of square roots in certain rings of power series,Math. Ann.158 (1965), 82-89, doi:10.1007/bf01370732. · Zbl 0136.02503
[12] G. Chapuy, M. Marcus and G. Schaeffer, A bijection for rooted maps on orientable surfaces, SIAM J. Discrete Math.23(2009), 1587-1611, doi:10.1137/080720097. · Zbl 1207.05087
[13] P. Flajolet and A. Odlyzko, Singularity analysis of generating functions,SIAM J. Discrete Math. 3(1990), 216-240, doi:10.1137/0403019. · Zbl 0712.05004
[14] Z. Gao, The number of rooted2-connected triangular maps on the projective plane,J. Comb. Theory Ser. B53(1991), 130-142, doi:10.1016/0095-8956(91)90058-r. · Zbl 0753.05043
[15] Z. Gao, The asymptotic number of rooted2-connected triangular maps on a surface,J. Comb. Theory Ser. B54(1992), 102-112, doi:10.1016/0095-8956(92)90068-9.
[16] Z. Gao and L. B. Richmond, Root vertex valency distributions of rooted maps and rooted triangulations,European J. Combin.15(1994), 483-490, doi:10.1006/eujc.1994.1050. · Zbl 0807.05026
[17] Z. Gao and J. Wang, Exact enumeration of rooted3-connected triangular maps on the projective plane,Discrete Appl. Math.141(2004), 149-159, doi:10.1016/s0166-218x(03)00375-5. · Zbl 1042.05052
[18] Z. Gao and N. C. Wormald, The distribution of the maximum vertex degree in random planar maps,J. Comb. Theory Ser. A89(2000), 201-230, doi:10.1006/jcta.1999.3006. · Zbl 0944.05057
[19] I. P. Goulden and D. M. Jackson,Combinatorial Enumeration, A Wiley-Interscience Publication, John Wiley & Sons, New York, 1983. · Zbl 0519.05001
[20] H. Gr¨otzsch, Zur Theorie der diskreten Gebilde. VII. Ein Dreifarbensatz f¨ur dreikreisfreie Netze auf der Kugel,Wiss. Z. Martin-Luther-Univ. Halle-Wittenberg. Math.-Nat. Reihe8 (1958/1959), 109-120.
[21] J. P. Hutchinson, Automorphism properties of embedded graphs,J. Graph Theory8(1984), 35-49, doi:10.1002/jgt.3190080105. · Zbl 0534.05029
[22] F. Jaeger, Flows and generalized coloring theorems in graphs,J. Comb. Theory Ser. B26(1979), 205-216, doi:10.1016/0095-8956(79)90057-1. · Zbl 0422.05028
[23] F. Jaeger, Nowhere-zero flow problems, in: L. W. Beineke and R. J. Wilson (eds.),Selected Topics in Graph Theory 3, Academic Press, San Diego, California, pp. 71-95, 1988. · Zbl 0658.05034
[24] S. G. Krantz and H. R. Parks,The Implicit Function Theorem: History, Theory, and Applications, Modern Birkh¨auser Classics, Birkh¨auser/Springer, New York, 2013, doi:10.1007/ 978-1-4614-5981-1.
[25] V. A. Liskovets, Some asymptotical estimates for planar Eulerian maps,Combin. Probab. Comput.5(1996), 131-138, doi:10.1017/s0963548300001929. · Zbl 0861.05031
[26] Y. Liu, A polyhedral theory on graphs,Acta Math. Sinica (N. S.)10(1994), 136-142, doi: 10.1007/bf02580420. · Zbl 0812.05017
[27] Y. Liu, Combinatorial invariants on planar graphs,Acta Math. Sinica (N. S.)11(1995), 211- 220, doi:10.1007/bf02274063. · Zbl 0838.05038
[28] Y. Liu,Enumerative Theory of Maps, volume 468 ofMathematics and its Applications, Kluwer Academic Publishers, Dordrecht, 1999. · Zbl 0990.05070
[29] Y.-P. Liu,Rectilinear Embeddings: Theory and Methods (in Chinese), Science Press, Beijing, 1994.
[30] S. Long and H. Ren, Counting2-connected4-regular maps on the projective plane,Electron. J. Combin.21(2014), #P2.51 (24 pages),https://www.combinatorics.org/ojs/ index.php/eljc/article/view/v21i2p51.
[31] S. D. Long and H. Ren,4-edge-connected4-regular maps on the plane, Research-Report IMSU 90(2001).
[32] Maplesoft, a division of Waterloo Maple Inc., Maple,https://www.maplesoft.com/.
[33] A. Mednykh and R. Nedela, Enumeration of unrooted maps of a given genus,J. Comb. Theory Ser. B96(2006), 706-729, doi:10.1016/j.jctb.2006.01.005. · Zbl 1102.05033
[34] A. Mednykh and R. Nedela, Enumeration of unrooted hypermaps of a given genus,Discrete Math.310(2010), 518-526, doi:10.1016/j.disc.2009.03.033. · Zbl 1185.05082
[35] R. C. Mullin and P. J. Schellenberg, The enumeration ofc-nets via quadrangulations,J. Comb. Theory4(1968), 259-276, doi:10.1016/s0021-9800(68)80007-9.
[36] H. Ren and Y. Liu, On the number of regular maps on the projective plane,Util. Math.56 (1999), 201-209. · Zbl 0938.05033
[37] H. Ren and Y. Liu,4-regular maps on the Klein Bottle,J. Comb. Theory Ser. B82(2001), 118-137, doi:10.1006/jctb.2000.2030. · Zbl 1023.05077
[38] H. Ren and Y. Liu, Enumerating near-4-regular maps on the sphere and the torus,Discrete Appl. Math.110(2001), 273-288, doi:10.1016/s0166-218x(00)00251-1.
[39] H. Ren and Y. Liu, The number of loopless4-regular maps on the projective plane,J. Comb. Theory Ser. B84(2002), 84-99, doi:10.1006/jctb.2001.2064. · Zbl 1018.05046
[40] H. Ren, Y. Liu and Z. Li, Enumeration of2-connected loopless4-regular maps on the plane, European J. Combin.23(2002), 93-111, doi:10.1006/eujc.2001.0533.
[41] L. B. Richmond and N. C. Wormald, Almost all maps are asymmetric,J. Comb. Theory Ser. B 63(1995), 1-7, doi:10.1006/jctb.1995.1001. · Zbl 0820.05017
[42] W. T. Tutte, On the imbedding of linear graphs in surfaces,Proc. London Math. Soc.51(1949), 474-483, doi:10.1112/plms/s2-51.6.474. · Zbl 0033.30803
[43] W. T. Tutte, On the problem of decomposing a graph intonconnected factors,J. London Math. Soc.36(1961), 221-230, doi:10.1112/jlms/s1-36.1.221. · Zbl 0096.38001
[44] W. T. Tutte, A theory of3-connected graphs,Indag. Math. (Proceedings)64(1961), 441-455, doi:10.1016/s1385-7258(61)50045-5. · Zbl 0101.40903
[45] W. T. Tutte, A census of slicings,Canadian J. Math.14(1962), 708-722, doi:10.4153/ cjm-1962-061-1. · Zbl 0111.35202
[46] W. T. Tutte, A census of planar maps,Canadian J. Math.15(1963), 249-271, doi:10.4153/ cjm-1963-029-x. · Zbl 0115.17305
[47] W. T. Tutte, On the enumeration of planar maps,Bull. Amer. Math. Soc.74(1968), 64-74, doi:10.1090/s0002-9904-1968-11877-4. · Zbl 0157.31101
[48] W. T. Tutte,Graph Theory, volume 21 ofEncyclopedia of Mathematics and its Applications, Addison-Wesley, Reading, Massachusetts, 1984.
[49] T. R. S. Walsh, A. Giorgetti and A. Mednykh, Enumeration of unrooted orientable maps of arbitrary genus by number of edges and vertices,Discrete Math.312(2012), 2660-2671, doi: 10.1016/j.disc.2011.11.027. · Zbl 1246.05076
[50] T. R. S. Walsh and A. B. Lehman, Counting rooted maps by genus. I,J. Comb. Theory Ser. B 13(1972), 192-218, doi:10.1016/0095-8956(72)90056-1.
[51] T. R. S. Walsh and A. B. Lehman, Counting rooted maps by genus. II,J. Comb. Theory Ser. B 13(1972), 122-141, doi:10.1016/0095-8956(72)90049-4. · Zbl 0228.05109
[52] N.
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.