Kinh doanh - Marketing
Kinh tế quản lý
Biểu mẫu - Văn bản
Tài chính - Ngân hàng
Công nghệ thông tin
Tiếng anh ngoại ngữ
Kĩ thuật công nghệ
Khoa học tự nhiên
Khoa học xã hội
Văn hóa nghệ thuật
Sức khỏe - Y tế
Văn bản luật
Nông Lâm Ngư
Kỹ năng mềm
Luận văn - Báo cáo
Giải trí - Thư giãn
Tài liệu phổ thông
Văn mẫu
Giới thiệu
Đăng ký
Đăng nhập
Tìm
Danh mục
Kinh doanh - Marketing
Kinh tế quản lý
Biểu mẫu - Văn bản
Tài chính - Ngân hàng
Công nghệ thông tin
Tiếng anh ngoại ngữ
Kĩ thuật công nghệ
Khoa học tự nhiên
Khoa học xã hội
Văn hóa nghệ thuật
Y tế sức khỏe
Văn bản luật
Nông lâm ngư
Kĩ năng mềm
Luận văn - Báo cáo
Giải trí - Thư giãn
Tài liệu phổ thông
Văn mẫu
Thông tin
Điều khoản sử dụng
Quy định bảo mật
Quy chế hoạt động
Chính sách bản quyền
Giới thiệu
Đăng ký
Đăng nhập
0
Trang chủ
Luận Văn - Báo Cáo
Báo cáo khoa học
Báo cáo khoa học:Tight estimates for eigenvalues of regular graphs
tailieunhanh - Báo cáo khoa học:Tight estimates for eigenvalues of regular graphs
It is shown that if a d-regular graph contains s vertices so that the distance between any pair is at least 4k, then its adjacency matrix has at least s eigenvalues which are at least 2pd − 1 cos( 2k ). A similar result has been proved by Friedman using more sophisticated generally, Serre has shown (see [3], [4] ) that for any fixed r and for any infinite family of d-regular graphs Gi, lim inf r(Gi) 2pd − 1. The same result has been proved by Friedman already in [5]. | Tight estimates for eigenvalues of regular graphs A. Nilli Department of Mathematics Sackler Faculty of Exact Sciences Tel Aviv University Tel Aviv 69978 Israel nilli@ Submitted Apr 4 2004 Accepted May 3 2004 Published May 24 2004 MR Subject Classification 05C50 Abstract It is shown that if a d-regular graph contains s vertices so that the distance between any pair is at least 4k then its adjacency matrix has at least s eigenvalues which are at least 2ựd 1 cos n . A similar result has been proved by Friedman using more sophisticated tools. 1 The main result Let G V E be a simple d-regular graph on n vertices. let A be its adjacency matrix and let A1 G d A2 G . An G be its eigenvalues. Alon and Boppana 1 see also 9 11 proved that for any fixed d and for any infinite family of of d-regular graphs Gi liminf A2 Gi 2 ựd 1. This bound is sharp at least when d 1 is a prime congruent to 1 modulo 4 as shown by the construction of Lubotzky Phillips and Sarnak 9 obtained independently by Margulis 10 . In fact in 1 it is conjectured that almost all d-regular graphs G on n vertices satisfy A2 G 2ỵ d 1 o 1 as n tends to infinity . This has recently been proved by Friedman 6 . More generally Serre has shown see 3 4 that for any fixed r and for any infinite family of d-regular graphs Gi liminf Ar Gi 2 ựd 1. The same result has been proved by Friedman already in 5 . In this note we give an elementary simple proof of this result following the method of 11 . Our estimate is a bit better than that of 11 even for the case r 2 also studied by Kahale in 7 and matches in the first two terms the estimate of Friedman in 5 but the proof is completely elementary. Theorem 1 Let G be a d-regular graph containing s vertices so that the distance between any pair of them is at least 4k. Then As G 2 ựd 1 cos n . THE ELECTRONIC JOURNAL OF COMBINATORICS 11 2004 N9 1 2 The proof Let G V E be a d-regular graph where d 3. Let v E V be a vertex define Vo v and let V be the set of all vertices of
Vy Lan
100
4
pdf
Báo lỗi
Trùng lắp nội dung
Văn hóa đồi trụy
Phản động
Bản quyền
File lỗi
Khác
Upload
Tải xuống
đang nạp các trang xem trước
Bấm vào đây để xem trước nội dung
Tải xuống
TÀI LIỆU LIÊN QUAN
Báo cáo khoa học:Tight estimates for eigenvalues of regular graphs
4
77
0
TÀI LIỆU XEM NHIỀU
Một Case Về Hematology (1)
8
461870
55
Giới thiệu :Lập trình mã nguồn mở
14
22657
59
Tiểu luận: Tư tưởng Hồ Chí Minh về xây dựng nhà nước trong sạch vững mạnh
13
10896
529
Câu hỏi và đáp án bài tập tình huống Quản trị học
14
10069
446
Phân tích và làm rõ ý kiến sau: “Bài thơ Tự tình II vừa nói lên bi kịch duyên phận vừa cho thấy khát vọng sống, khát vọng hạnh phúc của Hồ Xuân Hương”
3
9524
104
Ebook Facts and Figures – Basic reading practice: Phần 1 – Đặng Tuấn Anh (Dịch)
249
8287
1125
Tiểu luận: Nội dung tư tưởng Hồ Chí Minh về đạo đức
16
8242
423
Mẫu đơn thông tin ứng viên ngân hàng VIB
8
7865
2220
Đề tài: Dự án kinh doanh thời trang quần áo nữ
17
6690
253
Vật lý hạt cơ bản (1)
29
5774
85
TỪ KHÓA LIÊN QUAN
Báo cáo khoa học
Tight estimates
eigenvalues
regular graphs
reports of mathematics
mathematical works
Even circuits
prescribed clockwise parity
Science (in Latin Scientia
meaning knowledge or understanding) is the efforts to implement the invention
and increased knowledge of the human understanding of how the operation of the physical world surroundings
Through controlled methods
scientists use to observe the signs of expression or of the material and unusual nature to collect data
analyze information to explain how it works
there at the phenomenon of things
One of the ways that test method to simulate natural phenomena under controlled conditions and tested ideas
Knowledge in science is the total amount of information that has accumulated research
The definition of science is accepted as common knowledge that science has been actively systematized
TÀI LIỆU MỚI ĐĂNG
Khóa luận tốt nghiệp: Giải pháp nâng cao chất lượng phương thức thanh toán tín dụng chứng từ phục vụ xuất nhập khẩu tại ngân hàng Thương mại Việt Nam - Trần Thị Tân
12
118
0
28-04-2024
MẪU CHỨNG CHỈ QUẢN LÝ VŨ KHÍ, VẬT LIỆU NỔ, CCHT
1
118
0
28-04-2024
Báo cáo nghiên cứu khoa học " HÃY LÀM CHO HUẾ XANH HƠN VÀ ĐẸP HƠN "
6
118
0
28-04-2024
Anh văn TOEFL Vocabulary-008
8
86
0
28-04-2024
Ngòi bút hiện thực của Nguyễn Minh Châu trong tác phẩm "Chiếc thuyền ngoài xa"
8
110
0
28-04-2024
Báo cáo y học: "Aggrecanases and cartilage matrix degradation"
10
92
0
28-04-2024
Báo cáo y học: "Regulation and localization of endogenous human tristetraprolin"
12
84
0
28-04-2024
Báo cáo y học: "ignal 3 and its role in autoimmunity"
2
94
0
28-04-2024
Báo cáo " Thực thi một số cam kết quốc tế của Việt Nam về biến đổi khí hậu "
9
117
0
28-04-2024
Phương pháp phân tích - Nhập môn kinh tế lượng với các ứng dụng
551
94
0
28-04-2024
TÀI LIỆU HOT
Mẫu đơn thông tin ứng viên ngân hàng VIB
8
7865
2220
Giáo trình Tư tưởng Hồ Chí Minh - Mạch Quang Thắng (Dành cho bậc ĐH - Không chuyên ngành Lý luận chính trị)
152
5747
1375
Ebook Chào con ba mẹ đã sẵn sàng
112
3768
1231
Ebook Tuyển tập đề bài và bài văn nghị luận xã hội: Phần 1
62
5325
1136
Ebook Facts and Figures – Basic reading practice: Phần 1 – Đặng Tuấn Anh (Dịch)
249
8287
1125
Giáo trình Văn hóa kinh doanh - PGS.TS. Dương Thị Liễu
561
3501
643
Tiểu luận: Tư tưởng Hồ Chí Minh về xây dựng nhà nước trong sạch vững mạnh
13
10896
529
Giáo trình Sinh lí học trẻ em: Phần 1 - TS Lê Thanh Vân
122
3687
525
Giáo trình Pháp luật đại cương: Phần 1 - NXB ĐH Sư Phạm
274
4055
516
Bài tập nhóm quản lý dự án: Dự án xây dựng quán cafe
35
4130
480
crossorigin="anonymous">
Đã phát hiện trình chặn quảng cáo AdBlock
Trang web này phụ thuộc vào doanh thu từ số lần hiển thị quảng cáo để tồn tại. Vui lòng tắt trình chặn quảng cáo của bạn hoặc tạm dừng tính năng chặn quảng cáo cho trang web này.