Báo cáo toán học: "Uniqueness of graph square roots of girth six"

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: Uniqueness of graph square roots of girth six. | Uniqueness of graph square roots of girth six Anna Adamaszek Department of Computer Science and Centre for Discrete Mathematics and its Applications DIMAP University of Warwick Coventry CV4 7AL UK annan@ Michal Adamaszek Warwick Mathematics Institute and Centre for Discrete Mathematics and its Applications DIMAP University of Warwick Coventry CV4 7AL UK aszek@ Submitted Dec 11 2009 Accepted Jun 22 2011 Published Jul 1 2011 Mathematics Subject Classifications 05C12 05C75 Abstract We prove that if two graphs of girth at least 6 have isomorphic squares then the graphs themselves are isomorphic. This is the best possible extension of the results of Ross and Harary on trees and the results of Farzad et al. on graphs of girth at least 7. We also make a remark on reconstruction of graphs from their higher powers. 1 Introduction For a simple undirected connected graph H its square G H2 is the graph on the same vertex set in which two distinct vertices are adjacent if their distance in H is at most 2. In this case H is called the square root of G. Also recall that the girth of a graph is the length of its shortest cycle or X for a tree . The neighbourhood NH u of u will be the set consisting of u and its adjacent vertices in H. By distH u v we denote the distance between two vertices in H. We investigate the uniqueness of square roots of graphs. Ross and Harary 5 proved the following theorem 1 If T1 and T2 are two trees such that T2 and T22 are isomorphic then T1 and T2 are isomorphic. Research of both authors supported by the EPSRC award EP D063191 1. THE ELECTRONIC JOURNAL OF COMBINATORICS 18 2011 P139 1 This was recently improved by the authors of 1 who proved 2 If H1 and H2 are two graphs of girth at least 7 such that H2 and H2 are isomorphic then Hl and H2 are isomorphic. In the next section we prove the best possible result which is 3 If H1 and H2 are two graphs of girth at least 6 such that H2 and H2 are isomorphic then H1 and H2 are .