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
Authors who publish in this journal agree to the following terms:
Authors retain copyright and grant the journal the right of first publication, with the work simultaneously licensed under the Creative Commons Attribution License that allows the sharing of the work with acknowledgment of authorship and initial publication in this journal.
Authors are authorized to assume additional contracts separately, for non-exclusive distribution of the version of the work published in this journal (eg, publish in an institutional repository or as a book chapter), with acknowledgment of authorship and initial publication in this journal.
Authors are allowed and encouraged to publish and distribute their work online (eg, in institutional repositories or on their personal page) at any point before or during the editorial process, as this can generate productive changes as well as increase impact and the citation of the published work (See The effect of open access).
This is an open access journal which means that all content is freely available without charge to the user or his/her institution. Users are allowed to read, download, copy, distribute, print, search, or link to the full texts of the articles, or use them for any other lawful purpose, without asking prior permission from the publisher or the
author. This is in accordance with the BOAI definition of open access
Intellectual Property
All the contents of this journal, except where otherwise noted, is licensed under a Creative Commons Attribution License under attribution BY.