TAILIEUCHUNG - Báo cáo toán học: "Growth of graph powers"

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: Growth of graph powers. | Growth of graph powers A. Pokrovskiy Departement of Mathematics London School of Economics and Political Sciences Houghton Street WC2A 2AE London United Kingdom. Submitted Nov 11 2010 Accepted Mar 23 2011 Published Apr 14 2011 Mathematics Subject Classification 05C12 Abstract For a graph G its rth power is constructed by placing an edge between two vertices if they are within distance r of each other. In this note we study the amount of edges added to a graph by taking its rth power. In particular we obtain that for r 3 either the rth power is complete or many new edges are added. In this direction Hegarty showed that there is a constant e 0 such e G3 1 e e G . We extend this result in two directions. We give an alternative proof of Hegarty s result with an improved constant of e 1. We also show that for general r e Gr 3 - 1 e G . 1 Introduction This note addresses some questions raised by P. Hegarty in 4 . In that paper he studied results about graphs inspired by the Cauchy-Davenport Theorem. All graphs in this paper are simple and loopless. For two vertices u v G V G denote the length of the shortest path between them by d u v . For v G V G define its ith neighborhood as Ni v u G V G d u v i . The rth power of a graph G denoted Gr is constructed from G by adding an edge between two vertices x and y when they are within distance r in G. Define the diameter of G diam G as the minimal r such that Gr is complete alternatively the maximal distance between two vertices . Denote the number of edges of G by e G . For v G V G and a set of vertices S define er v S u G S d v u r . The Cayley graph of a subset A c Zp is constructed on the vertex set Zp. For two distinct vertices x y G Zp we define xy to be an edge whenever x y G A or y x G A. Research supported by the LSE postgraduate research studentship scheme. THE ELECTRONIC JOURNAL OF COMBINATORICS 18 2011 P88 1 The following is a consequence of the Cauchy-Davenport Theorem usually stated in the .

• 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