Đang chuẩn bị liên kết để tải về tài liệu:
Báo cáo toán học: "A conjecture of Biggs concerning the resistance of a distance-regular graph"

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: A conjecture of Biggs concerning the resistance of a distance-regular graph. | A conjecture of Biggs concerning the resistance of a distance-regular graph Greg Markowsky gmarkowsky@gmail.com Pohang Mathematics Institute POSTECH Pohang 790-784 Republic of Korea Jacobus Koolen jacobus_koolen@yahoo.com Department of Mathematics POSTECH Pohang 790-784 Republic of Korea Submitted Apr 12 2010 Accepted May 18 2010 Published May 25 2010 Mathematics Subject Classification 05E30 Abstract Biggs conjectured that the resistance between any two points on a distanceregular graph of valency greater than 2 is bounded by twice the resistance between adjacent points. We prove this conjecture give the sharp constant for the inequality and display the graphs for which the conjecture most nearly fails. Some necessary background material is included as well as some consequences. 1 Introduction The main goal of this paper is to prove the following conjecture of Biggs Theorem 1 Let G be a distance-regular graph with degree larger than 2 and diameter D. If dj is the electric resistance between any two vertices of distance j then 1 max dj dD Kd1 j where K 1 -94 1.931. Equality holds only in the case of the Biggs-Smith graph. We remark that for degree 2 the theorem is trivially false. This theorem implies several statements concerning random walks on distance-regular graphs which will be given at the end of the paper. General background material on the concept of electric resistance as well as its connection to random walks can be found in the excellent references 6 and 2 . Biggs conjecture originally appeared in 1 which discusses electric resistance on distance-regular graphs only. To understand the proof of the conjecture one must THE ELECTRONIC JOURNAL OF COMBINATORICS 17 2010 R78 1 understand much of the material in 1 . We have therefore decided to include the material from 1 which is key to Theorem 1. This appears in Section 3 following the relevant graph-theoretic definitions in Section 2. Section 4 gives our proof of the theorem and Section 5 gives some .