The preservation property of Brouwer’s conjecture | [Discrete Mathematics Letters • 2025]

Author(s):

1. Zhen Lin: School of Mathematics and Statistics, Qinghai Normal University,Xining, Qinghai,China

2. Ke Wang: School of Mathematics and Statistics, Qinghai Normal University,Xining, Qinghai,China

Abstract:

Let G be a simple graph with n vertices and e(G) edges. Brouwer's conjecture states that the sum of the k largest Laplacian eigenvalues of G is at most e(G) + k22+k for k = 1, 2, . . . , n. Torres and Trevisan [Linear Algebra Appl. 685 (2024) 66-76] showed that if Brouwer's conjecture holds for two simple graphs G1 and G2, then it also holds for the Cartesian product of G1 and G2. Inspired by this result, we say that an operation on G1 and G2 satisfies the preservation property of Brouwer's conjecture when the following statement is true: if Brouwer's conjecture holds for G1 and G2, then Brouwer's conjecture also holds for the graph obtained by applying the operation under consideration on G1 and G2. In this paper, we study the preservation property of Brouwer's conjecture under some edge addition operations, and hence we extend the results of Wang, Huang, and Liu [Math. Comput. Model. 56 (2012) 60-68].

Page(s): 39-45

DOI: 10.47443/dml.2024.164

Published: Journal: Discrete Mathematics Letters, Volume: 15, Issue: 0, Year: 2025

Keywords:

Brouwers conjecture , graph operation , Laplacian eigenvalue

References:

[1] Bai H. .2011 .The Grone-Merris conjecture. Trans. Amer. Math. Soc, 363 : 4463-4474.

[2] Berndsen J. .2012 .. Master's thesis, : .

[3] Brouwer A. E.,Haemers W. H. .2012 .. , : .

[4] Chen X. .2018 .Improved results on Brouwer's conjecture for sum of the Laplacian eigenvalues of a graph. Linear Algebra Appl, 557 : 327-338.

[5] Chen X. .2019 .On Brouwer's conjecture for the sum of k largest Laplacian eigenvalues of graphs. Linear Algebra Appl, 578 : 402-410.

[6] Chen X.,Li J.,Y. Fan, J. .2018 .Note on an upper bound for sum of the Laplacian eigenvalues of a graph. Linear Algebra Appl, 541 : 258-265.

[7] Cooper J. N. .2021 .Constraints on Brouwer's Laplacian spectrum conjecture. Linear Algebra Appl, 615 : 11-27.

[8] Du Z.,Zhou B. .2012 .Upper bounds for the sum of Laplacian eigenvalues of graphs. Linear Algebra Appl, 436 : 3672-3683.

[9] Fan K. .1949 .On a theorem of Weyl concerning eigenvalues of linear transformations I, Proc. Nat. Acad. Sci. USA, 35 : 652-655.

[10] Fritscher E.,Hoppen C.,Rocha I.,Trevisan V. .2011 .On the sum of the Laplacian eigenvalues of a tree. Linear Algebra Appl, 435 : 371-399.

[11] Fritscher E.,Hoppen C.,Rocha I.,Trevisan V. .2014 .Characterizing trees with large Laplacian energy. Linear Algebra Appl, 442 : 20-49.

[12] Ganie H. A.,Alghamdi A. M.,Pirzada S. .2016 .On the sum of the Laplacian eigenvalues of a graph and Brouwer's conjecture. Linear Algebra Appl, 501 : 376-389.

[13] Ganie H. A.,Pirzada S.,Rather B. A. .2021 .On Laplacian eigenvalues of graphs and Brouwer's conjecture. J. Ramanujan Math. Soc, 36 : 13-21.

[14] Ganie H. A.,Pirzada S.,Rather B. A.,Trevisan V. .2020 .Further developments on Brouwer's conjecture for the sum of Laplacian eigenvalues of graphs. Linear Algebra Appl, 588 : 1-18.

[15] Ganie H. A.,Pirzada S.,Shaban R. U.,Li X. .2019 .Upper bounds for the sum of Laplacian eigenvalues of a graph and Brouwer's conjecture. Discrete Math. Algorithms Appl, 11 : 1950028.

[16] Ganie H. A.,Pirzada S.,Trevisan V. .2021 .On the sum of k largest Laplacian eigenvalues of a graph and clique number. , 18 : 15.

[17] Grone R.,Merris R. .1994 .The Laplacian spectrum of a graph II, SIAM J. , 7 : 221-229.

[18] Guan M.,Zhai M.,Wu Y. .2014 .On the sum of two largest Laplacian eigenvalue of trees. J. Inequal. Appl, : 242.

[19] Haemers W. H.,Mohammadian A.,Tayfeh-Rezaie B. .2010 .On the sum of Laplacian eigenvalues of graphs. Linear Algebra Appl, 432 : 2214-2221.

[20] A. K. Kelmans .1967 .The properties of the characteristic polynomial of a graph, Cybernetics-in the service of Communism 4 (. , : 27-41.

[21] Kumar P.,Merajuddin S.,Pirzada S. .2023 .Computing the sum of k largest Laplacian eigenvalues of tricyclic graphs. Discrete Math. Lett, 11 : 14-18.

[22] Li W.,Guo J. .2022 .On the full Brouwer's Laplacian spectrum conjecture. , 345 : 113078.

[23] Liu Y.,Shao J.,X. Yuan, J. .2008 .Some results on the ordering of the Laplacian spectral radii of unicyclic graphs. Discrete Appl. Math, 156 : 2679-2697.

[24] Mayank .2010 .On Variants of the Grone-Merris Conjecture, Master thesis. , : .

[25] Pirzada S.,Ganie H. A. .2015 .On the Laplacian eigenvalues of a graph and Laplacian energy. Linear Algebra Appl, 486 : 454-468.

[26] Radenkovic´ S.,I. Gutman S. .2007 .Total π -electron energy and Laplacian energy: how far the analogy goes?. J. Serb. Chem. Soc, 72 : 1343-1350.

[27] Rocha I.,Trevisan V. .2014 .Bounding the sum of the largest Laplacian eigenvalues of graphs, Discrete Appl. , 170 : 95-103.

[28] Torres G. S.,Trevisan V. .2024 .Brouwer's conjecture for the Cartesian product of graph. Linear Algebra Appl, 685 : 66-76.

[29] Wang S.,Huang Y.,Liu B. .2012 .On a conjecture for the sum of Laplacian eigenvalues. Math. Comput. Model, 56 : 60-68.

[30] Yu A.,Lu M.,Tian F. .2005 .Ordering trees by their Laplacian spectral radii. Linear Algebra Appl, 405 : 45-59.

Citations

Downloads

Views