NEW UPPER BOUND ON THE LARGEST LAPLACIAN EIGENVALUE OF GRAPHS
Abstract
Let G = (V;E) be a simple, undirected graph with maximum and minimum degree ∆ and respectively, and let A be the adjacency matrix and Q be the Laplacianmatrix of G. In the past decades, the Laplacian spectrum has received much more and more attention, since it has been applied to several elds, such as randomized algorithms, combinatorial optimization problems and machine learning. In this paper, we compute lower and upper bounds for the largest Laplacian eigenvalue which is related with a given maximum and minimum degree and a given number of vertices and edges. We also compare our results in this paper with some known results.
Keywords
Full Text:
PDFReferences
F. R. K. Chung, Spectral Graph Theory, in: CBMS Regional Conference Series in Mathematics, vol. 92, Published for the Conference Board of the Mathematical Sciences, Washington, DC, 1997.
D. M. Cvetkovi´ c M. Doob, H. Sachs, Spectra of Graphs Theory and Applications, third ed., Johann Ambrosius Barth, Heidelberg, 1995.
E. R. van Dam W. H. Haemers, Which graphs are determined by their spectrum? Linear Algebra Appl. 373 (2003) 241–272.
W. N. Anderson T. D. Morely, Eigenvalues of the Laplacian of a graph, Linear Multilinear Algebra 18 (1985) 141–145.
M. Fiedler, A property of eigenvectors of nonnegative symmetric matrices and its application to graph theory, Czechoslovak Math. J. 25 (1975) 607 – 618.
R. Merris, Laplacian matrices of graphs: a survey, Linear Algebra Appl. 197–198 (1994) 143 – 176.
H. S. Wilf, The eigenvalues of a graph and its chromatic number, J. London Math. Soc. 42 (1967) 330 – 332.
A. J. Hoffman, On eigenvalues and colorings of graphs, in “Graph Theory and Its Applications” (B. Harris, ed.), Acad. Press, 1970, pp. 79 – 91.
M. Fiedler, Algebraic connectivity of graphs, Czech. Math. J. 23 (98) (1973) 298–305.
W. E. Donath, A. J. Hoffman, Lower bounds for the partitioning of graphs, IBM J. Res. Develop. 17 (1973) 420–425.
L. Lovász, On the Shannon capacity of a graph, IEEE Trans. Inform. Theory IT – 25 (1979) 1 – 7.
N. Alon, V. D. Milman, λ 1 , isoperimetric inequalities for graphs and superconcentrators, J. Combin.Theory, Ser. B 38 (1985) 73–88.
F. Juhász, On a method of cluster analysis, ZAMM 64 (1984) T335 – T336.
M. E. Dyer, A. Frieze, R. Kannan, A random polynomial-time algorithm for approximating the volume of convex bodies J. Assoc. Comput. Mach. 38 (1991) 1 – 17.
L. Lovász, M. Simonovits, The mixing rate of Markov chains, an isoperimetric inequality, and computing the volume, 31st Ann. Symp. FOCS, 1990, pp. 346 – 354.
L. Lovász, M. Simonovits, Random walks in a convex body and an improved volume algorithm, Random Struct. Algorithms 4 (1993) 359 – 412.
A. Sinclair, Algorithms for Random Generation and Counting: A Markov Chain Approach, Birkhauser, Boston, 1993.
N. Alon, Eigenvalues and expanders, Combinatorics 6 (1986) 83 – 96.
L. S. Shi, Bounds on the (Laplacian) spectral radius of graphs, Linear Algebra Appl. 422 (2007) 755 – 770.
D. Stevanovi´ c, The largest eigenvalue of nonregular graphs, J. Combin. Theory Ser.
B 91 (1) (2004) 143 – 146.
W. N. Anderson, T. D. Morley, Eigenvalues of the Laplacian of a graph,Linear and Multilinear Algebra 18 (1985) 141 – 145.
J. S. Li, X. D. Zhang, A new upper bound for eigenvalues of the Laplacian matrix of graphs, Linear Algebra Appl. 265 (1997) 93 – 100.
R. Merris, A note on Laplacian graph eigenvalues, Linear Algebra Appl. 285 (1998) 33 – 35.
J. S. Li, X. D. Zhang, On Laplacian eigenvalues of a graph, Linear Algebra Appl. 285 (1998) 305 – 307.
O. Rojo, R. Soto, H. Rojo, An always nontrival upper bound for Laplacian graph eigenvalues, Linear Algebra Appl. 312 (2000) 155 – 159.
Y. L. Pan, Sharp upper bounds for the Laplacian graph eigenvalues, Linear Algebra Appl. 355 (2002) 287 – 295.
K. Ch. Das, An improved upper bound for the Laplacian graph eigenvalues, Linear Algebra Appl. 368 (2003) 269 – 278.
Dongmei Zhu,On upper bounds for Laplacian graph eigenvalues, Linear Algebra and its Applications 432 (2010) 2764 – 2772.
Zhang, X. D. , 2007, The Laplacian eigenvalues of graphs: a survey. Gerald D. Ling (Ed.), Linear Algerbra Research Advances, Nova Science Publishers Inc. Chapter 6, pp. 201 – 228.
DOI: https://doi.org/10.22190/FUMI2002533T
Refbacks
- There are currently no refbacks.
ISSN 0352-9665 (Print)