Teoria Espectral dos Grafos: um Híbrido entre a Álgebra Linear e a Matemática Discreta e Combinatória com Origens na Química Quântica
DOI:
https://doi.org/10.5540/tema.2005.06.01.0001Abstract
A partir de um breve histórico da Teoria Espectral dos Grafos, TEG, este artigo apresenta os conceitos básicos da teoria e mostra como é possível, com o uso de simples resultados da álgebra Linear, determinar propriedades de um grafo através da correspondência entre a estrutura do grafo e o espectro de sua matriz de adjacência ou de sua matriz laplaciana. Além disso, indica alguns relacionamentos de TEG com outros ramos da Matemática, das Engenharias e da Ciência da Computação, apresenta uma série de problemas em aberto e aponta os possíveis desenvolvimentos da área.References
[1] N.M.M. Abreu e C.S. Oliveira, “Álgebra Linear em Teoria dos Grafos”, minicurso, Primeira Semana da Matemática de São Mateus, ERMAC/SBMAC, UFES, 2004.
S. Belhaiza, N.M.M. Abreu, P. Hansen e C.S. Oliveira, Variable Neighborhood Search for Extremal Graphs 11. Bounds on Algebraic Connectivity, apresentado em Computer and Discovery, Montreal, Canadá, submetido à série DIMACS, 2004.
K. Bali´nska, D. Cvetkovi´c, Z. Radosavljevi´c, S. Simi´c e D. Stevanovi´c, A survey on integral graphs, Publ. Elektrotehn. Fak. Ser. Mat., Univ. Belgrad , 13 (2002), 42-65.
N. Biggs, “Algebraic Graph Theory”, 2a. ed., Cambridge, Inglaterra, 1993.
L. Brankovic e D. Cvetkovi´c, The eigenspace of the eigenvalue -2 in generalized line graphs and a problem in security of statistical data bases, Publ. Elektrotehn. Fak. Ser. Mat., Univ. Belgrad, 14, (2003).
P.O. Boaventura Netto, “Grafos: Teoria, Modelos, Algoritmos”, 2a. ed., Editora Bl¨ucher, São Paulo, 2001.
D. Cvetkovi´c, M. Cangalovic e V. Kovacevic-Vujcic, Combinatorial optimization and highly informative graph invariants, to appear.
D. Cvetkovi´c, M. Doob, I. Gutman e A. Torgaˇsev, “Recent Results in the Theory of Graph Spectra”, North-Holland, 1988.
D. Cvetkovi´c, M. Doob e H. Sachs, “Spectra of Graphs: Theory and application”, Academic Press, New York, 1979.
D. Cvetkovi´c, M. Doob e H. Sachs, “Spectra of Graphs”, 3a. ed., Academic Press, New York, 1995.
D. Cvetkovi´c, P. Hansen e V. Kovacevic-Vujcic, On some interconnections between combinatorial optimization and extremal graph theory, to appear.
D. Cvetkovic, P. Rowlinson e S. Simic, “Eigenspaces of Graphs”, in: Encyclopedia of Mathematics and its Applications, Cambridge, vol. 66, 1997.
D. Cvetkovi´c, P. Rowlinson e S. Simic, “Spectral Generalizations of line graphs: On graphs with least eigenvalues-2”, Cambridge University Press, 2004.
D. Cvetkovi´c e D. Stevanovic, Spectral moments of fullerene graphs, MATCH
Commun. Math. Comput. Chem., 50 (2004), 62-72.
D. Cvetkovi´c, The Theory of Graph Spectra: Origins and Development, palestra apresentada em Algraic Graph Theory Jorney, ERMAC-Rio, SBMAC, (2004).
E.R. Dam e W.H. Haemers, Which graphs are determined by their spectrum, Linear Algebra and its Applications, 373 (2003) 241-272.
R. Diestel, “Graph Theory”, Springer-Verlag, 1997.
F.R. Gantmacher, “The Theory of Matrices”, Chelsea Publishing Company, New York, 1997.
A. Graovac, I. Gutman e N. Trinajsti´c, Graph theory and molecular orbitals, Theoret. Chim. Acta, 26 (1972), 67-78.
C. Godsil e G. Royle, “Algebraic Graph Theory”, Graduate texts in Mathematics, GTM 207, Springer, 2001.
F. Harary, “Graph Theory”, Addison-Wesley, 1969.
K. Hoffman e R. Kunze, “Linear Algebra”, Prentice-Hall Inc., 1961.
L. Lima, N.M.M. Abreu, P.E. Moraes e C. Sertã, Some properties of graphs in (a,b)-linear classes, submetido à Congressus Numerantium, 2004.
R. Merris, Laplacian Matrices of Graphs: A Survey, Linear Algebra and its Applications, 197/198 (1994), 143-176.
P.E. Moraes, N.M.M. Abreu e S. Jurkiewicz, The fifth and sixth coeficients of charactersitic polynomial of a graph, Eletronic Notes in Discrete Mathematics, 11, (2002).
G. Michaels e K.H. Rosen, “Applications of Discrete Mathematics”, Mc Graw- Hill, 1992.
C.S. Oliveira, N.M.M. Abreu e S. Jurkiewicz, The characteristic polynomial of the Laplacian graphs in (a,b)-linear classes, Linear Algebra and its Applications, 356 (2002), 113-121.
J.L. Szwarcfiter, “Grafos e Algoritmos Computacionais”, Ed. Campus, 1984.
N. Trinajsti´c, “Chimical Graph Theory”, I and II, CRC Press, Boca Raton, Flórida, 1983.
D.B. West, “Introduction to Graph Theory”, Prentice-Hall, 1996.
Downloads
Published
How to Cite
Issue
Section
License
Copyright
Authors of articles published in the journal Trends in Computational and Applied Mathematics retain the copyright of their work. The journal uses Creative Commons Attribution (CC-BY) in published articles. The authors grant the TCAM journal the right to first publish the article.
Intellectual Property and Terms of Use
The content of the articles is the exclusive responsibility of the authors. The journal uses Creative Commons Attribution (CC-BY) in published articles. This license allows published articles to be reused without permission for any purpose as long as the original work is correctly cited.
The journal encourages Authors to self-archive their accepted manuscripts, publishing them on personal blogs, institutional repositories, and social media, as long as the full citation is included in the journal's website version.
