TAILIEUCHUNG - Báo cáo toán học: "Densities of Minor-Closed Graph Families"

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:Densities of Minor-Closed Graph Families. | Densities of Minor-Closed Graph Families David Eppstein Computer Science Department University of California Irvine Irvine California USA Submitted Jul 1 2010 Accepted Sep 22 2010 Published Oct 15 2010 Mathematics Subject Classification 05C83 Primary 05C35 05C42 Secondary Abstract We define the limiting density of a minor-closed family of simple graphs F to be the smallest number k such that every n-vertex graph in F has at most kn 1 o 1 edges and we investigate the set of numbers that can be limiting densities. This set of numbers is countable well-ordered and closed its order type is at least w. It is the closure of the set of densities of density-minimal graphs graphs for which no minor has a greater ratio of edges to vertices. By analyzing density-minimal graphs of low densities we find all limiting densities up to the first two cluster points of the set of limiting densities 1 and 3 2. For multigraphs the only possible limiting densities are the integers and the superparticular ratios i i 1 . 1 Introduction Planar simple graphs with n vertices have at most 3n 6 edges. Outerplanar graphs have at most 2n 4 edges. Friendship graphs have 3 n 1 2 edges. Forests have at most n 1 edges. Matchings have at most n 2 edges. Where do the coefficients 3 2 3 2 1 and 1 2 of the leading terms in these bounds come from Planar graphs forests outerplanar graphs and matchings all form instances of minor-closed families of simple graphs families of the graphs with the property that any minor of a graph G in the family a simple graph formed from G by contracting edges and removing edges and vertices remains in the family. The friendship graphs graphs in the form of n 1 2 triangles sharing a common vertex are not minor-closed but are the maximal graphs in another minor-closed family the graphs formed by adding a single vertex to a matching. For any minor-closed family F of simple graphs there exists a number k such that every n-vertex graph in F has at most kn 1 o 1 edges 7 18 19 .

• Báo cáo khoa học
• báo cáo của tạp chí Department of Mathematic
• tài liệu báo cáo nghiên cứu khoa học
• cách trình bày báo cáo
• kiến thức toán học
• báo cáo toán học