Đ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 hay nhất của tạp chí toán học quốc tế đề tài: A LOWER BOUND FOR THE NUMBER OF EDGES IN A GRAPH CONTAINING NO TWO CYCLES OF THE SAME LENGTH. | A LOWER BOUND FOR THE NUMBER OF EDGES IN A GRAPH CONTAINING NO TWO CYCLES OF THE SAME LENGTH Chunhui Lai Dept. of Math. Zhangzhou Teachers College Zhangzhou Fujian 363000 P. R. of CHINA. zjlaichu@public.zzptt.fj.cn Submitted November 3 2000 Accepted October 20 2001. MR Subject Classifications 05C38 05C35 Key words graph cycle number of edges Abstract In 1975 P. Erdos proposed the problem of determining the maximum number f n of edges in a graph of n vertices in which any two cycles are of different lengths. In this paper it is proved that f n n 32t 1 for t 27720r 169 r A 1 and n A 6911t2 5144411 3309665 Conseouentlv lol b t Í I I -Lvj _J I -L anu In 16 b I 8 b 16 . onsuquunLly lim inf . f n n 2 2562 liminfn 1 pn 2 6911 1 Introduction Let f n be the maximum number of edges in a graph on n vertices in which no two cycles have the same length. In 1975 Erdos raised the problem of determining f n see 1 p.247 Problem 11 . Shi 2 proved that f n n p8n 23 1 2 for n 3. Lai 3 4 5 6 proved that for n 1381 9 t2 26 45 t 98 45 t 360q 7 f n n 19t 1 Project Supported by NSF of Fujian A96026 Science and Technology Project of Fujian K20105 and Fujian Provincial Training Foundation for Bai-Quan-Wan Talents Engineering . THE ELECTRONIC JOURNAL OF COMBINATORICS 8 2001 N9 1 and for n e2m 2m 3 4 f n n 2 ựnln 4n 2m 3 2n log2 n 6 . Boros Caro Fiiredi and Yuster 7 proved that f n n 1.98ựn 1 o 1 . Let v G denote the number of vertices and e G denote the number of edges. In this paper we construct a graph G having no two cycles with the same length which leads to the following result. Theorem. Let t 27720r 169 r 1 then f n n 32t 1 fnr n. 6911t2 5144411 lox n 16 t 8 t 3309665 16 2 Proof of Theorem Proof. Let. t 27720r 169. r 1. n 691112 514441 t 3309665. n n. We shall show X J- JoJ. 1 Jvi1 o 111 I I J-kJ f Ả. nt 16 h I 8 v 16 n nịt VVe sẤẤaẤẤ sấấow that there exists a graph G on n vertices with n 32t 1 edges such that all cycles in G have distinct lengths. Now we construct the graph G which .
