Đang chuẩn bị liên kết để tải về tài liệu:
Báo cáo toán học: "A Differential Approach for Bounding the Index of Graphs under Perturbations"

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 Differential Approach for Bounding the Index of Graphs under Perturbations. | A Differential Approach for Bounding the Index of Graphs under Perturbations C. Dalfo M.A. Fiol E. Garriga Departament de Matematica Aplicada IV Universitat Politecnica de Catalunya cdalf o fiol egarriga @ma4.upc.edu Submitted Mar 24 2011 Accepted Aug 22 2011 Published Sep 2 2011 Mathematics Subject Classification 05C50 47A55 . Abstract This paper presents bounds for the variation of the spectral radius A G of a graph G after some perturbations or local vertex edge modifications of G. The perturbations considered here are the connection of a new vertex with say g vertices of G the addition of a pendant edge the previous case with g 1 and the addition of an edge. The method proposed here is based on continuous perturbations and the study of their differential inequalities associated. Within rather economical information namely the degrees of the vertices involved in the perturbation the best possible inequalities are obtained. In addition the cases when equalities are attained are characterized. The asymptotic behavior of the bounds obtained is also discussed. For instance if G is a connected graph and Gu denotes the graph obtained from G by adding a pendant edge at vertex u with degree ỗu then A G A G y3G o ãAõ Keywords. Graph Adjacency matrix Spectral radius Graph perturbation Differential inequalities. 1 Introduction When we represent a graph by its adjacency matrix it is natural to ask how the properties of the graph are related to the spectrum of the matrix. As is well-known the spectrum does not characterize the graph that is there are nonisomorphic cospectral graphs. However important properties of the graph stem from the knowledge of its spectrum. A summary of these relations can be found in Schwenk and Wilson 12 and in a THE ELECTRONIC JOURNAL OF COMBINATORICS 18 2011 P172 1 more extensive way in Cvetkovic Doob and Sachs 3 and Cvetkovic Doob Gutman and Torgasev 2 . The perturbation of a graph G is to be thought of as a local modification such as the .