Tuyển tập các báo cáo nghiên cứu khoa học ngành toán học tạp chí Department of Mathematic dành cho các bạn yêu thích môn toán học đề tài: Maxmaxflow and Counting Subgraphs. | Maxmaxflow and Counting Subgraphs Bill Jackson School of Mathematical Sciences Queen Mary University of London Mile End Road London E1 4NS England Alan D. Sokal Department of Physics New York University 4 Washington Place New York NY 10003 USA SOKAL@ Submitted Sep 28 2009 Accepted Jun 28 2010 Published Jul 10 2010 Mathematics Subject Classification 05C99 Primary 05C15 05C30 05C35 05C40 82B20 90B10 Secondary Abstract We introduce a new graph invariant A G that we call maxmaxflow and put it in the context of some other well-known graph invariants notably maximum degree and its relatives. We prove the equivalence of two dual definitions of maxmaxflow one in terms of flows the other in terms of cocycle bases. We then show how to bound the total number or more generally total weight of various classes of subgraphs of G in terms of either maximum degree or maxmaxflow. Our results are motivated by a conjecture that the modulus of the roots of the chromatic polynomial of G can be bounded above by a function of A G . Key Words Graph subgraph flow cocycle maxmaxflow maximum degree second-largest degree degeneracy number chromatic polynomial. Also at Department of Mathematics University College London London WC1E 6BT England. THE ELECTRONIC JOURNAL OF COMBINATORICS 17 2010 R99 1 Contents 1 Introduction 2 2 Maxmaxflow 4 3 Cocycle Bases and Maxmaxflow 7 4 Some Preliminaries 12 Pointwise bounds vs. generating-function bounds . 12 Convex hulls in graphs. 12 5 Counting Walks and Paths 13 6 Counting Trees and Forests 18 The classes Tm X and Fm X Y . 18 The class Hm X . 22 7 Counting Connected Subgraphs and Related Objects 24 8 Counting Blocks Block Paths Block Trees and Block Forests 29 The classes BTm X BFm X Y and BFm X Y . 30 The class Bm X . 42 1 Introduction An elementary result on graph colouring is that the chromatic number x G of a graph G is at most one more than the maximum degree A G . A much deeper result is that the .
