tailieunhanh - Báo cáo toán học: "Graph Minors and Minimum Degree"

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: Graph Minors and Minimum Degree. | Graph Minors and Minimum Degree Gasper Fijavz Faculty of Computer and Information Science University of Ljubljana Ljubljana Slovenia David R. Wood Department of Mathematics and Statistics The University of Melbourne Melbourne Australia woodd@ Submitted Dec 7 2008 Accepted Oct 22 2010 Published Nov 5 2010 Mathematics Subject Classifications 05C83 graph minors Abstract Let Dk be the class of graphs for which every minor has minimum degree at most k. Then Dk is closed under taking minors. By the Robertson-Seymour graph minor theorem Dk is characterised by a finite family of minor-minimal forbidden graphs which we denote by Dk. This paper discusses Dk and related topics. We obtain four main results 1. We prove that every k 1 -regular graph with less than 4 k 2 vertices is in Dk and this bound is best possible. 2. We characterise the graphs in Dk 1 that can be obtained from a graph in Dk by adding one new vertex. 3. For k 3 every graph in Dk is k 1 -connected but for large k we exhibit graphs in Dk with connectivity 1. In fact we construct graphs in Dk with arbitrary block structure. 4. We characterise the complete multipartite graphs in Dk and prove analogous characterisations with minimum degree replaced by connectivity treewidth or pathwidth. . is supported by a QEII Research Fellowship from the Australian Research Council. An extended abstract of this paper was published in Proc. Topological Geometric Graph Theory TGGT 08 Electronic Notes in Discrete Mathematics 31 79-83 2008. THE ELECTRONIC JOURNAL OF COMBINATORICS 17 2010 R151 1 1 Introduction The theory of graph minors developed by Robertson and Seymour 25 is one of the most important in graph theory influencing many branches of mathematics. Let X be a minor-closed class of graphs1. A graph G is a minimal forbidden minor of X if G is not in X but every proper minor of G is in X. Let X be the set of minimal forbidden minors of X. By the graph minor theorem of Robertson