The Contradiction Argument for the Brouwer Conjecture

André Luis Andrejew Ferreira, Débora Marília Hauenstein, Guilherme Porto

Resumo


In this work we develop results to contribute to the study of the Brouwer conjecturethrough an argument of contradiction. Specifically, if the Brouwer conjecture is not valid for agraph and this graph respects some conditions, we show that the conjecture is also not valid for thegraphs obtained by deleting an edge or vertex. In this way, we can recursively delete certain verticesand edges of the original graph until the resulting graph is in a family for which the conjecture isproven, a contradiction.

Palavras-chave


Brouwer Conjecture; Laplacian Eigenvalues; Spectral Graph Theory

Texto completo:

PDF (English)

Referências


Anderson, W. N. and Morley, T. D. Eigenvalues of the Laplacian of a graph,Linear andMultilinear Algebra, 18:141-145, 1985. DOI: 10.1080/03081088508817681.

Bai, H. The grone-merris conjecture.Transactions of the American Mathematical Society,363:4463-4474, 2011. DOI: 10.2307/23032227.

Berndsen, J. and Blokhuis, A. Three problems in algebraic combinatorics, Disserta ̧c ̃ao deMestrado, Eindhoven University of Technology, 2012.

Brouwer, A. E. and Haemers, W. H.Spectra of graphs. Springer, New York, 2012.

Du, Z. and Zhou, B. Upper bounds for the sum of Laplacian eigenvalues of graphs,LinearAlgebra and its Applications, 436:3672-3683, 2012. DOI: 10.1016/j.laa.2012.01.007.

Fritscher, E., Hoppen, C., Rocha, I. and Trevisan, V. On the sum of the Lapla-cian eigenvalues of a tree,Linear Algebra and its Applications, 435:371-399, 2011. DOI:10.1016/j.laa.2011.01.036

Grone, R. and Merris, R. The Laplacian spectrum of a graph II,SIAM Journal on discretemathematics, 7:221-229, 1994. DOI: 10.1137/S0895480191222653.

Haemers, W. H., Mohammadian, A. and Tayfeh-Rezaie, B. On the sum of Laplacianeigenvalues of graphs,Linear Algebra and its Applications, 432:2214-2221, 2010. DOI:10.1016/j.laa.2009.03.038.

Hall, F., Patel, K. and Stewart, M. Interlacing results on matrices associated with graphs,Journal of Combinatorial Mathematics and Combinatorial Computing, 68:113-127, 2009. DOI:10.1027/25632223433.

Helmberg, C. and Trevisan, V. Threshold graphs of maximal Laplacian energy,Discrete Math-ematics, 338:1075-1084, 2015. DOI: 10.1016/j.disc.2015.01.025.

Mayank, O. Variants of the Grone–Merris conjecture, Disserta ̧c ̃ao de Mestrado, EindhovenUniversity of Technology, 2010.

Merris, R. Laplacian matrices of graphs: a survey,Linear Algebra and its Applications,197:143-176, 1994. DOI: 10.1016/0024-3795(94)90486-3.

Van Den Heuvel, J. Hamilton cycles and eigenvalues of graphs,Linear algebra and its appli-cations, 226:723-730, 1995. DOI: 10.1016/0024-3795(95)00254-O.

Wang, S., Huang, Y. and Liu, B. On a conjecture for the sum of Laplacian eigenvalues,Mathematical and Computer Modelling, 56:60-68, 2012. DOI: 10.1016/j.mcm.2011.12.047.

Zhang, X. D. The Laplacian eigenvalues of graphs: a survey,arXiv preprint arXiv:1111.2897,2011.




DOI: https://doi.org/10.5540/03.2021.008.01.0484

Apontamentos

  • Não há apontamentos.


SBMAC - Sociedade de Matemática Aplicada e Computacional
Edifício Medical Center - Rua Maestro João Seppe, nº. 900, 16º. andar - Sala 163 | São Carlos/SP - CEP: 13561-120
 

Normas para publicação | Contato