Tuyển tập các báo cáo nghiên cứu khoa học về toán học trên tạp chí toán học quốc tế đề tài: Explicit enumeration of triangulations with multiple boundaries. | Explicit enumeration of triangulations with multiple boundaries Maxim Krikun Institut Elie Cartan Universite Henri Poincare . 239 54506 Vandreuvre-les-Nancy France krikun@ Submitted Jun 5 2007 Accepted Aug 14 2007 Published Aug 27 2007 Mathematics Subject Classihcation 05C30 Abstract We enumerate rooted triangulations of a sphere with multiple holes by the total number of edges and the length of each boundary component. The proof relies on a combinatorial identity due to . Tutte. 1 Introduction Definitions A planar map is a class of equivalence of embedded graphs G S2 by the homeomorphisms of S2. We note by V G E G and F G the sets of vertices edges and faces of the the map G respectively. A map with holes is a pair G H H c F G such that no two faces h h0 2 H share a common vertex and all vertices at the boundary of hi 2 H are distinct . the boundary of hi is a simple cycle . In the following we refer to the faces h 2 H as holes. A map is called a triangulation if every face of F G H has degree 3. If H 0 such triangulation is called a complete triangulation. In the following we will consider rooted triangulations that is triangulations with one distinguished directed edge called the root. In addition to that we assume that the holes of a triangulation are enumerated by integers 0 . r and that the root is always located at the boundary of the 0-th hole. Main result In this paper we solve explicitly the recursive equations for generating functions planar triangulations with arbitrary number of holes in terms of the total number of edges and the length of each boundary component. THE ELECTRONIC JOURNAL OF COMBINATORICS 14 2007 R61 1 The class of triangulations we consider is the most wide possible the underlying graph may contain multiple edges and loops. Although this class is sometimes thought of as pathological it turns out that the presence of loops is a feature which greatly simplifies the calculations involved . compared to 6 .
