Đang chuẩn bị liên kết để tải về tài liệu:
Báo cáo toán học: "Automorphism groups of a graph and a vertex-deleted subgraph"
Đ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 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:Automorphism groups of a graph and a vertex-deleted subgraph. | Automorphism groups of a graph and a vertex-deleted subgraph Stephen G. Hartke Hannah Kolb Jared Nishikawa Derrick Stolee Submitted Sep 17 2009 Accepted Sep 24 2010 Published Oct 5 2010 Mathematics Subject Classification 05C60 Keywords automorphism group reconstruction Cayley graph isomorph-free generation. Abstract Understanding the structure of a graph along with the structure of its subgraphs is important for several problems in graph theory. Two examples are the Reconstruction Conjecture and isomorph-free generation. This paper raises the question of which pairs of groups can be represented as the automorphism groups of a graph and a vertex-deleted subgraph. This and more surprisingly the analogous question for edge-deleted subgraphs are answered in the most positive sense using concrete constructions. 1 Introduction The Reconstruction Conjecture of Ulam and Kelley famously states that the isomorphism class of all graphs on three or more vertices is determined by the isomorphism classes of its vertex-deleted subgraphs see GH69 for a survey of classic results on this problem . A frequent issue when attacking reconstruction problems is that automorphisms of the substructures lead to ambiguity when producing the larger structure. This paper considers the relation between the automorphism group of a graph and the automorphism groups of the vertex-deleted subgraphs and edge-deleted subgraphs. If a group r1 is the automorphism group of a graph G and another group r2 is the Department of Mathematics University of Nebraska Lincoln Nebraska 68688-0130 USA hartke@math.unl.edu. This author was supported in part by a Nebraska EPSCoR First Award and by National Science Foundation grant DMS-0914815. Department of Mathematics University of Illinois Urbana Illinois 61801 USA hkolb2@illinois.edu. Department of Mathematics University of Colorado Boulder Colorado 80309 USA jared.nishikawa@colorado.edu. Department of Mathematics Department of Computer Science University of .