Đang chuẩn bị liên kết để tải về tài liệu:
Báo cáo toán học: "Edge-bandwidth of the triangular grid"
Đ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 về toán học trên tạp chí toán học quốc tế đề tài: Edge-bandwidth of the triangular grid. | Edge-bandwidth of the triangular grid Reza Akhtar Dept. of Mathematics and Statistics Miami University Oxford OH 45056 USA reza@calico.mth.muohio.edu Tao Jiang Dept. of Mathematics and Statistics Miami University Oxford OH 45056 USA jiangt@muohio.edu Dan Pritikin Dept. of Mathematics and Statistics Miami University Oxford OH 45056 USA pritikd@muohio.edu Submitted May 19 2006 Accepted Aug 16 2007 Published Oct 5 2007 Mathematics Subject Classification 05C78 Abstract In 1995 Hochberg McDiarmid and Saks proved that the vertex-bandwidth of the triangular grid Tn is precisely n 1 more recently Balogh Mubayi and Pluhár posed the problem of determining the edge-bandwidth of Tn. We show that the edge-bandwidth of Tn is bounded above by 3n 1 and below by 3n o n . 1 Introduction A labeling of the vertices of a finite graph G is a bijective map h V G 1 2 . V G . The vertex-bandwidth of h is defined as B G h max h u h v u v eE G and the vertex-bandwidth or simply bandwidth of G is defined as B G min B G h h THE ELECTRONIC JOURNAL OF COMBINATORICS 14 2007 R67 1 in which the minimum is taken over all labelings of V G . The edge-bandwidth of G is defined as B G B L G where L G is the line graph of G. Edge-bandwidth has been studied for several classes of graphs in various sources among them 1 2 5 and 6 . In this article we study the edge-bandwidth of the triangular grid Tn. For any integer n 0 Tn is the graph whose vertices are ordered triples of nonnegative integers summing to n with an edge connecting two triples if they agree in one coordinate and differ by 1 in the other two see Figure 1 for an illustration of T5 the bottom row vertices from left to right being 0 5 0 1 4 0 2 3 0 3 2 0 4 1 0 and 5 0 0 . The vertexbandwidth of Tn was studied by Hochberg McDiarmid and Saks in 4 they proved that B Tn n 1. The problem of determining B0 Tn was posed by Balogh Mubayi and Pluhár in 1 . Our main result is Theorem 1.1. 3n o n B0 Tn 3n 1. It is easy to obtain the stated upper bound on .