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: The number of graphs not containing K3,3 as a minor. | The number of graphs not containing K3 3 as a minor Stefanie Gerke Omer Gimenezy Marc Noyy Andreas Weifilz Submitted Feb 25 2008 Accepted Aug 31 2008 Published Sep 8 2008 Mathematics Subject Classification 05C30 05A16 Abstract We derive precise asymptotic estimates for the number of labelled graphs not containing K33 as a minor and also for those which are edge maximal. Additionally we establish limit laws for parameters in random K3 3-minor-free graphs like the number of edges. To establish these results we translate a decomposition for the corresponding graphs into equations for generating functions and use singularity analysis. We also End a precise estimate for the number of graphs not containing the graph K3 3 plus an edge as a minor. 1 Introduction We say that a graph is K3 3-minor-free if it does not contain the complete bipartite graph K3 3 as a minor. In this paper we are interested in the number of simple labelled K3 3-minor-free and maximal K3 3-minor-free graphs where maximal means that adding any edge to such a graph yields a K3 3-minor. It is known that there exists a constant c such that there are at most cnn K3 3-minor-free graphs on n vertices. This follows from a result of Norine et al. 13 which prove such a bound for all proper graph classes closed under taking minors. This gives also an upper bound on the number of maximal K3 3-minor-free graphs as they are a proper subclass of K3 3-minor-free graphs. In 11 McDiarmid Steger and Welsh give conditions where an upper bound of the form cnn on the number of graphs Cn on n vertices in a graph class C yields that Cn n n c 0 as n 1. These conditions are satisfied for K3 3-minor-free graphs but not in the case of maximal K3 3-minor-free graphs as one condition requires that two disjoint copies of a graph of the class in question form again a graph of the class. Royal Holloway University of London Egham Surrey TW20 0EX UK . y Universitat Politècnica de Catalunya Jordi Girona 1-3 .
