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

N.M.M. de Abreu

doi:10.5540/tema.2005.06.01.0001

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

N.M.M. de Abreu

Abstract

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.

Full Text:

PDF (Português (Brasil))

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.

DOI: https://doi.org/10.5540/tema.2005.06.01.0001