tailieunhanh - Báo cáo toán học: " Some Applications of the Proper and Adjacency Polynomials in the Theory of Graph Spectra"

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í toán học quốc tế đề tài: Some Applications of the Proper and Adjacency Polynomials in the Theory of Graph Spectra. | Some Applications of the Proper and Adjacency Polynomials in the Theory of Graph Spectra . Fiol Departament de Matemàtica Aplicada i Telemàtica Universitat Politècnica de Catalunya Jordi Girona 1-3 Màdul C3 Campus Nord 08034 Barcelona Spain email fiol@ Submitted February 22 1997 Accepted September 15 1997. Abstract Given a vertex u 2 V of a graph r V E the local proper polynomials constitute a sequence of orthogonal polynomials constructed from the so-called u-local spectrum of r. These polynomials can be thought of as a generalization for all graphs of the distance polynomials for the distance-regular graphs. The local adjacency polynomials which are basically sums of proper polynomials were recently used to study a new concept of distance-regularity for non-regular graphs and also to give bounds on some distance-related parameters such as the diameter. Here we develop the subject of these polynomials and gave a survey of some known results involving them. For instance distance-regular graphs are characterized from its spectrum and the number of vertices at extremal distance from each of their vertices. Afterwards some new applications of both the proper and adjacency polynomials are derived such as bounds for the radius of r and the weight k-excess of a vertex. Given the integers k i 0 let r u denote the set of vertices which are at distance at least k from a vertex u 2 V and there exist exactly 1 shortest k-paths from u to each of such vertices. As a main result an upper bound for the cardinality of Ffc u is derived showing that r u decreases at least as 0 1-2 and the cases in which the bound is attained are characterized. When these results are particularized to regular graphs with four distinct eigenvalues we reobtain a result of Van Dam about 3-class association schemes and prove some conjectures of Haemers and Van Dam about the number of vertices at distance three from every vertex of a regular graph with four distinct eigenvalues setting k 2 .