TAILIEUCHUNG - Báo cáo toán học: "Nonexistence of graphs with cyclic defect"

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: Nonexistence of graphs with cyclic defect. | Nonexistence of graphs with cyclic defect Mirka Miller t School of Electrical Engineering and Comp. Science University of Newcastle Australia Department of Mathematics University of West Bohemia Czech Republic Department of Computer Science King s College London UK Submitted Nov 10 2010 Accepted Mar 9 2011 Published Mar 31 2011 Mathematics Subject Classification 05C35 05C75 Abstract In this note we consider graphs of maximum degree A diameter D and order M A D 2 where M A D is the Moore bound that is graphs of defect 2. In 1 Delorme and Pineda-Villavicencio conjectured that such graphs do not exist for D 3 if they have the so called cyclic defect . Here we prove that this conjecture holds. Keywords Graphs with cyclic defect Moore bound defect repeat. 1 Nonexistence of graphs with cyclic defect Let G be a graph of maximum degree A diameter D and order M A D 2 where M A D 1 A A A 1 A A 1 2 A A 1 D-1 is the Moore bound that is graphs of defect 2. In such a graph G any vertex v can reach within D steps either two vertices called repeats of v in two different ways each or one vertex called double repeat of v in three different ways all the other vertices of G are reached from v in at most D steps in exactly one way. The repeat multi graph of G R G consists of the vertex set V G and there is an edge u v in R G if and only if v is a repeat of u and vice versa in G. Clearly when defect is 2 R G is either one cycle of length n V G or a disjoint union of cycles whose sum of lengths is equal to n. If R G is cycle of length n then we say that G has cyclic defect. Interest in such graphs is part of the general study of the . edu. au Iphis research was supported by a Marie Curie International Incoming Fellowship within the 7th European Community Framework Programme THE ELECTRONIC JOURNAL OF COMBINATORICS 18 2011 P71 1 degree diameter problem. For a survey of this problem see 4 . Graphs with cyclic defect were first studied by Fajtlowicz 2 who proved that .

• 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