Article
Full entry |
PDF
(0.3 MB)
Feedback
PDF
(0.3 MB)
Feedback
Keywords:
planar Eulerian triangulation; Latin bitrade; Latin square
planar Eulerian triangulation; Latin bitrade; Latin square
Summary:
A planar Eulerian triangulation is a simple plane graph in which each face is a triangle and each vertex has even degree. Such objects are known to be equivalent to spherical Latin bitrades. (A Latin bitrade describes the difference between two Latin squares of the same order.) We give a classification in the near-regular case when each vertex is of degree $4$ or $6$ (which we call a near-homogeneous spherical Latin bitrade, or NHSLB). The classification demonstrates that any NHSLB is equal to two graphs embedded in hemispheres glued at the equator, where each hemisphere belongs to one of nine possible types, each of which may be described recursively.
References:
[1] Altshuler A.: Construction and enumeration of regular maps on the torus. Discrete Math. 115 (1973), 201–217. DOI 10.1016/S0012-365X(73)80002-0 | MR 0321797 | Zbl 0253.05117
[2] Batagelj V.: An improved inductive definition of a restricted class of triangulations of the plane. Combinatorics and Graph Theory (Warsaw, 1987), Banach Center Publ., 25, PWN, Warsaw, 1989, pp. 11–18. MR 1097631
[3] Brinkmann G., McKay B.: Guide to using plantri. version 4.1 http://cs.anu.edu.au/ bdm/plantri/.
[4] Cavenagh N.: The theory and application of Latin bitrades: a survey. Math. Slovaca 58 (2008), 691–718. DOI 10.2478/s12175-008-0103-2 | MR 2453264 | Zbl 1199.05020
[5] Cavenagh N.: A uniqueness result for $3$-homogeneous Latin trades. Comment. Math. Univ. Carolin. 47 (2006), 337–358. MR 2241536 | Zbl 1138.05007
[6] Cavenagh N., Lisonek P.: Planar Eulerian triangulations are equivalent to spherical Latin bitrades. J. Combin. Theory Ser. A 115 (2008), 193–197. DOI 10.1016/j.jcta.2007.04.002 | MR 2378864 | Zbl 1131.05019
[7] Colbourn C.J., Dinitz J.H., Wanless I.M.: Latin Squares. in: The CRC Handbook of Combinatorial Designs, 2nd ed. (C.J. Colbourn and J.H. Dinitz, eds.), CRC Press, Boca Raton, FL, 2007, pp. 135–152.
[8] Drápal A., Griggs T.S.: Homogeneous Latin bitrades. Ars Combin. 96 (2010), 343–351. MR 2666820
[9] Goodey P.R.: Hamiltonian circuits in polytopes with even sided faces. Israel J. Math. 22 (1975), 52–56. DOI 10.1007/BF02757273 | MR 0410565 | Zbl 0317.05114
[10] Grannell M.J., Griggs T.S., Knor M.: Biembeddings of symmetric configurations and $3$-homogeneous Latin trades. Comment. Math. Univ. Carolin. 49 (2008), 411–420. MR 2490436
[11] Grünbaum B.: Convex Polytopes. John Wiley, New York, 1967. MR 0226496 | Zbl 1033.52001
[12] Holton D.A., Manvel B., McKay B.D.: Hamiltonian cycles in $3$-connected bipartite planar graphs. J. Combin. Theory Ser. B 38 (1985), 279–297. DOI 10.1016/0095-8956(85)90072-3 | MR 0796604
[13] Lovász L.: Combinatorial Problems and Exercises. 2nd edition, North-Holland, Amsterdam, 1993. MR 1265492 | Zbl 1120.05001
[14] Negami S.: Uniqueness and faithfulness of embedding of toroidal graphs. Discrete Math. 44 (1983), 161–180. DOI 10.1016/0012-365X(83)90057-2 | MR 0689809 | Zbl 0508.05033
[15] Saaty T.L., Kainen P.L.: The Four-Colour Problem: Assaults and Conquests. McGraw-Hill, New York, 1977. MR 0480047
[16] Tutte W.T. (Ed.): Recent Progresses in Combinatorics. Academic Press, New York, 1969, p. 343. MR 0250896
[17] Wanless I.: A computer enumeration of small Latin trades. Australas. J. Combin. 39 (2007), 247–258. MR 2351205 | Zbl 1138.05009
Search
Partner of
