Đang chuẩn bị nút TẢI XUỐNG, xin hãy chờ
Tải xuống
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: On the number of genus one labeled circle trees. | On the number of genus one labeled circle trees Karola Meszaros Massachusetts Institute of Technology karola@math.mit.edu Submitted Sep 25 2005 Accepted Sep 17 2007 Published Oct 5 2007 Mathematics Subject Classihcation 05C30 05C75 05C10 05A99 Abstract A genus one labeled circle tree is a tree with its vertices on a circle such that together they can be embedded in a surface of genus one but not of genus zero. We dehne an e-reduction process whereby a special type of subtree called an e-graph is collapsed to an edge. We show that genus is invariant under e-reduction. Our main result is a classihcation of genus one labeled circle trees through e-reduction. Using this we prove a modihed version of a conjecture of David Hough namely that the number of genus one labeled circle trees on n vertices is divisible by n or n 2. Moreover we explicitly characterize when each of these possibilities occur. 1 Introduction Graphical enumeration arises in a variety of contexts in combinatorics 2 and naturally so in the realm of combinatorial objects with interesting topological properties 5 . We provide a new classification of genus one circle trees and address a question raised by Hough 3 about their number. Our study is motivated by numerous results in the study of partitions and trees of a certain genus as well as results about the genuses of maps and hypermaps 1 6 7 8 . The following two definitions are discussed in 3 in great detail we shall use the definition of a labeled circle tree throughout the paper whereas we shall mostly use an alternate less technical definition for the genus of a circle tree. Definition 1. A labeled circle tree l-c-tree on n points is a tree with its n vertices labeled 1 through n on a circle in a counterclockwise direction and its edges drawn as straight lines within the circle. THE ELECTRONIC JOURNAL OF COMBINATORICS 14 2007 R68 1 Definition 2. The genus g of a l-c-tree T on n points is defined to be g a 1 2 n-1-z a z a 1 ơ where a is the matching
